Check for palindrome using recursion

Question

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

Your algorithm is correct, but you need to `return check(a[1:len(a)-1])`. — tptcat, May 07 '16 at 06:47
You can tighten your code a smidgeon by checking `len(a) < 2` in the first `if`, and by using negative indexing (`a[-1]` and `a[1:-1]`) in the second. — pjs, May 07 '16 at 16:22

score 0 · Accepted Answer · edited May 23 '17 at 12:23

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

I think you should add an end condition when the palindrom is even ("erre" would return false if I'm not mistaken). — Pierre.Sassoulas, May 08 '16 at 07:27
@Pierre.Sassoulas good suggestion; confirming, though, that "erre" returns True as written. — Daniel, May 08 '16 at 07:36
Upon further examination I think that "a[1:-1]" if 'a' is an array of length 1, return an array of length 0 and does not throw errors, so it works. My bad. — Pierre.Sassoulas, May 08 '16 at 08:55
@Daniel can you please give an example of duplication in the palindrome example — user2375245, May 10 '16 at 21:59

Check for palindrome using recursion

1 Answers1

Bonus Info