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

    Join Date
    Nov 2013
    Posts
    15
    Rep Power
    0

    Question 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. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,894
    Rep Power
    481

    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.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo