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 . Im using Python.
11 Answers
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] 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 :)
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.
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]) Here's another viewpoint
A palindromic string is
Some letter, x.
Some palindromic substrinng.
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.
Some leading punctuation. Some letter, x.
Some palindromic substring.
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.
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.
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; My solution
#To solve this I'm using the stride notation within a slice [::] def amazonPalindrome(input): inputB = input input = input[::-1] #print input noPalindrome = inputB + " is not a palindrome" isPalindrome = inputB + " is a palindrome" #compare the value of the reversed string to input string if input[0]!= input[-1]: print noPalindrome else: print isPalindrome #invoking the def requires at least 1 value or else it fails #tests include splitting the string,mixing integers, odd amount palindromes. #call the def amazonPalindrome('yayay') a=raw_input("enter the string:") b=len(a) c=0 for i in range(b): if a[i]==a[-(i+1)]: c=c+1 if c==b: print a,"is polindrome" else: print a,"is not polindrome" 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" Here is C version, if anyone happens to land here searching for C code!
int IsPalindrome_Recursive(char *s, int start, int end) { if ((end - start) < 2) { return 1; } if (s[start] != s[end]) { return 0; } return IsPalindrome_Recursive(s, ++start, --end); } Call as:
IsPalindrome_Recursive(s, 0, strlen(s) - 1) 
