Recursive Function palindrome in Python

Question

I need help writing a recursive function which detects whether a string is a palindrome. But i can't use any loops it must be recursive. Can anyone help show me how this is done. I need to learn this for an upcoming midterm. Im using Python.

Answer 1

From a general algorithm perspective, the recursive function has 3 cases:

1) 0 items left. Item is a palindrome, by identity.

2) 1 item left. Item is a palindrome, by identity.

3) 2 or more items. Remove first and last item. Compare. If they are the same, call function on what's left of string. If first and last are not the same, item is not a palindrome.

The implementation of the function itself is left as an exercise to the reader :)

Answer 2

If a string is zero or one letters long, it's a palindrome.

If a string has the first and last letters the same, and the remaining letters (I think it's a [1: -1] slice in Python, but my Python is a bit rusty) are a palindrome, it's a palindrome.

Now, write that as a palindrome function that takes a string. It will call itself.

Answer 3

Here's another viewpoint

A palindromic string is

1. Some letter, x.

2. Some palindromic substrinng.

3. The same letter, x, repeated.

Also, note that you may be given a proper English sentence "Able was I ere I saw Elba." with punctuation. Your palindrome checker may have to quietly skip punctuation. Also, you may have to quietly match without considering case. This is slightly more complex.

1. Some leading punctuation. Some letter, x.

2. Some palindromic substring.

3. Some letter, x, repeated without regard to case. Some trailing punctuation.

And, by definition, a zero-length string is a palindrome. Also a single-letter string (after removing punctuation) is a palindrome.

Answer 4

The function should expect a string. If there is more then one letter in the string compare the first and the last letter. If 1 or 0 letters, return true. If the two letters are equal call the function then again with the string, without the first and the last letter. If they are not equal return false.

 palindrom( word):
   IF length of word 1 or 0 THEN
      return 0;
   IF last and first letter equal THEN
     word := remove first and last letter of word;
     palindrom( word);
   ELSE
     return false;

Answer 5

Here's a way you can think of simple recursive functions... flip around the problem and think about it that way. How do you make a palindrome recursively? Here's how I would do it...

def make_palindrome():
    maybe:
        return ""
    elsemaybe:
        return some_char()
    else:
        c = some_char()
        return c + make_palindrome() + c

Then you can flip it around to build the test.

Answer 6

def ispalindrome(word):
    if len(word) < 2: return True
    if word[0] != word[-1]: return False
    return ispalindrome(word[1:-1])

And here is the best one liner

def ispalindrome(word):
    return word == word[::-1]

Answer 7

Since we're posting code anyway, and no one-liner has been posted yet, here goes:

def palindrome(s):
    return len(s) < 2 or s[0] == s[-1] and palindrome(s[1:-1])

Answer 8

n=raw_input("Enter a number===>") n=str(n) l=len(n) s="" for i in range(1,l+1): s=s+n[l-i] if s==n: print "Given number is polindrom" else: print "Given number is not polindrom"