How does this recursion work in python?

Question

I watched a video a couple of hours ago on recursion in python and then recreated the program which was made in the video so it worked in my version of Python. The code works but there is a bit I don't understand fully and what it is doing.

def lower(s):
    s = s.lower()
    return s

def isPal(s):
    if len(s) <= 1:
        return True
    else:
        return s[0] == s[-1] and isPal(s[1:-1])

def isPalindrome(s):
    if isPal(lower(s)) == True:
        print("{0} is a palindrome".format(s))

The part which I am having an issue with is the

return s[0] == s[-1] and isPal(s[1:-1])

What I am wondering is why are they being returned and also why is it s[1:-1] and not s[0:-1] if you think you know of any good places which would help simplify recursions for me feel free to share them. Thanks in advance.

Answer 1

why is it s[1:-1] and not s[0:-1]

s[1:-1] returns s with the first and last element chopped off. s[0:-1] returns s with just the last element chopped off.

You need to chop off both ends to preserve the palindrome property (if it is a palindrome), which is that elements equidistant from the middle are identical. If you chop off only one end, you move the middle, which would (in the general case) destroy that invariant.

This goes to the heart of self recursion: you do a thing, then you delegate a simpler case which has the same properties.

Why return s[0] == s[-1] and isPal(s[1:-1])

This is being returned because it first checks that the first and last elements have the palindrome property (as above) AND that the next "layer" also has that property. If the outer pair is not equal it is not a palindrome, and False will be returned; if it is true, the recursive step is taken, and if that is True, the expression as a whole returns True.

Answer 2

Imagine you have the word 'kayak'

The program will look if :

'k' == 'k' if yes the program will call the function with : 'aya'

Then the program will look if 'a' == 'a' if yes the program will call the function with 'y'

Then it's only one letter, So the program returns True

Answer 3

This is where the magic happens:

return (s[0] == s[-1]) and isPal(s[1:-1])

(I have added parentheses, so you are absolutely clear on the operator precedence). It is important to know that the Python AND statement will evaluate the first argument, and only if it is True, will it evaluate the second argument. If the first was False, then it will return False immediately without calling isPal(). This is known as short-circuit evaluation. Blender makes a good example of this in his post.

s[0] is the first letter in the string, s[-1] is the last letter in the sting. First we check to see if the first and last letters are the same. If they are different, then there is no way the string can be a palindrome. If the are the same we can disregard them and move onto the inner part of the string.

s[1:-1] trims off the first and last letters, and then passes that to the isPal() function, which happens to be the function we are currently in -- this is called recursion. When we 'recurse' into the function again, a new stack is created, new local variables are created, and the input arguments to the function will be different to the ones in the previous call.

We continue to check the first and last letters, and recurse all the way to the centre of the word. At this point there are either 1 or 0 characters left, and if we have got that far we know we have found a palindrome.

When we return from this final, inner, call to isPal() the return value (True if a palindrome has been found) is passed to the calling function, which then returns it to its calling function, etc., until the final 'outside' isPal() function returns the result to the initial caller. We call this process 'unrolling the stack'.

Here is an example:

s = 'racecar'
s[0] == s[-1] # True - both letters are 'r'
s = s[1:-1]   # s becomes 'aceca'
s[0] == s[-1] # True - both letters are 'a'
s = s[1:-1]   # s becomes 'cec'
s[0] == s[-1] # True - both letters are 'c'
s = s[1:-1]   # s becomes 'e'
len(s) <= 1   # This statement is now True, so the stack will start to unwind

Visually, the calls will look like this:

'racecar' ---------
                  |
                  V    'aceca'
 True <--- isPal(   ) ----
             ^           |
        True |           V     'cec'
             ---- isPal(   ) ----
                    ^           |
               True |           V     'e'
                    ---- isPal(   ) ----
                           ^           |
                      True |           V
                           ---- isPal(   )  # We get all the way down here,
                                            # and then we start to return

In the case where we do not have a palindrome, this will happen:

'race2car' --------
                  |
                  V    'ace2ca'
False <--- isPal(   ) ----
             ^           |
       False |           V     'ce2c'
             ---- isPal(   ) ----
                    ^           |
              False |           V     'e2'
                    ---- isPal(   ) ----
                           ^           |
                     False |           V
                           ---- isPal(   )  # Here the outer two letters
                                            # do not match, so we start to
                                            # return False

Answer 4

You are checking if the first and last of s are the same, so once you do that you slice them off and check if the next first and last are the same by returning, the recursive part, and it keeps adding together the result until there is 1 or less letters in s. It then returns what you have gathered so far and True.

Adding a print(s) on the line before if len(s) <= 1: or a print(s[0] == s[-1] and isPal(s[1:-1])) after the else: may help you understand the recursion more.

Answer 5

That step uses the short-circuiting logical AND, so it really acts like this:

if s[0] != s[-1]:
    return False
else:
    return isPal(s[1:-1])

As for s[1:-1], you compare the first and last characters with s[0] != s[-1], so s[1:-1] just removes the first and last characters and passes the resulting string back into isPal.