### Thread: Help with python recursion

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2013
Posts
15
Rep Power
0

#### Help with python recursion

Hello everyone,
I created a program that check's if the input is a palindrome, if it is, it returns true, else it is false.
( I must use recursion)
This is my code:

str="abaa"
def is_palindrome(str):
n=len(str)
if n==0:
return True

if str[n-1]==str[-n]:

is_palindrome(str[-(n)+1:n-1])
return True
else:
return False

Now, the problem is, that for some reason, it does not work properly. I checked it on python tutor, and for some reason unknown to me, it made all the inputs as true.
I thank you very much for your help.
2. #### yet another "it fails"

Why oh why is it so difficult for people to explain what the problem is?

First we'll write test code. Here I've used the doctest module. Run doctests from the command line interpreter with command
Code:
CLI_PROMPT\$ python -m doctest python_program.py
Tests show what your program ought to do and they document an expected use. Furthermore, and depending on how extensive the tests are, tests assure program correctness. Exercising the tests validates your program.

I installed doctests lists containing objects of different data types. This shows the generality of the program. Palindromes are structural.

The doctests contain edge cases of 0 length list, a test for length 1 input, and both yeah and neah palindromes tests for length 2, and for longer lists of even and odd length. The comprehensivity of these tests satisfies me.

Now let's fix your code. Your algorithmic intent appears to test the equality of two objects, then try recursively with the shortened list, but messed up the indexing. It should work. It does work with proper implementation.

Use the subscript 0 to access the first item of a list.
Subscript -1 accesses the last item. And don't mask the name of a builtin. I removed str.
Code:
def is_palindrome(candidate):
'''
>>> L = list(range(3))
>>> is_palindrome(L)
False
>>> is_palindrome(L + list(reversed(L)))
True
>>> ([is_palindrome(test_data) for test_data in
...     ('',  'a',  'bib', 'ab',  'abc', 'gohangasalamiimalasagnahog', )] ==
...     [True, True, True, False, False, True,                         ])
...
True
'''
if candidate:                         # a list is True if it has non-zero length
if candidate[0] == candidate[-1]: # compare first and last items
return is_palindrome(candidate[1:-1])   # RETURN the value from the recursive call
return False                                # You could write "else: return False" but I don't.
return True                                     # 0 length list is a palindrome.

test_data = "abaa"
print("""`"{}" is palindromic'...{}...""".format(test_data, is_palindrome(test_data)))
Last edited by b49P23TIvg; November 8th, 2013 at 06:57 AM.