user2375245 - 2 years ago 113
Python Question

# Check for palindrome using recursion

I have used the following code for checking whether a string is palindrome. However it is returning None when a string is palindrome.

``````def check(a):

if len(a)==1 or len(a)==0:
return True
if a[0]==a[len(a)-1]:
check(a[1:len(a)-1])
else:
return False

``````

You need to return the result of the recursion in your function:

``````def check(a):
# Base Case
if len(a) < 2:
return True

# Recursive Call
if a[0] == a[-1]:
check(a[1:-1])
else:
return False

return check(a[1:-1])

``````

## Bonus Info

Your function performs duplicate work as it checks the string `a`. To avoid duplicate function calls and greatly improve the performance of your algorithm, you might consider memoization. Otherwise, you could build up a large call stack and potentially cause a stack overflow error (hey, that's the name of the website...).

Here's one possible way to implement memoization, by constructing a class around your function:

``````class check:
def __init__(self):
self.memo = {}

def Check(self, a):
# Base Case
if len(a) < 2:
return True

# Check Memo
if a in self.memo:
return self.memo[a]

# Recursive Call
if a[0] == a[-1]:
self.Check(a[1:-1])
else:
return False

# Memoize
self.memo[a] = True

return self.Check(a[1:-1])

print check().Check("rats live on no evil star")
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download