user2375245 user2375245 - 6 months ago 42
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




print check("radar")

Answer

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])

print check("radar")

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")