Recursion on string: What does the line 'return s[0] == s[-1] and isPal(s[1:-1])' do?

user_10334196 0
Viewed 431

I am currently going through 6.00.1x with MITx and recursion of string, but the following code really confuses me. This is supposed to tell whether a string is a palindrome (one which reads the same backward as forward), with abcba as a test string I use:

def isPalindrome(s):

    def toChars(s):
        s = s.lower()
        ans = ''
        for c in s:
            if c in 'abcdefghijklmnopqrstuvwxyz':
                ans = ans + c
        return ans

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

    return isPal(toChars(s))

isPalindrome('abcba')

The line return s[0] == s[-1] and isPal(s[1:-1]) really confuses me: I ran it on Python Tutor and it seems that upon running this line the first time, it goes recursively first, ie cutting out bcb and c, then as c would be the base case, it returns true and likewise for bcb.

2 things I am confused:

  1. Why does it go recursively the first time when it runs this line of code? s[0] == s[-1] should return a Boolean value T/F, but this seems to have been ignored till it reaches the base case?

  2. So the recursion runs till it reaches the base case - that I get, but then the s[0] == s[-1] doesn't start running only till it reaches here...why? And how did the syntax of the code instruct the computer to evaluate s[0] == s[-1] on bcb?

recursion python
1 Answers

Well you have to think through this step by step:

  1. You pass abcba to isPalindrome
  2. isPalindrome calls isPal(toChars(s))
  3. toChars(s) returns "abcba" so this is passed to isPal(..)
  4. isPal is called with the argument "abcba".
  5. Check: is len(s)<=1? No, len(s) is 5.
  6. So to else: is s[0] == s[-1]? Yes. If it wasn't, this function would stop right here and return False. But now to the next step.
  7. Since s[0] == s[-1] is True we need to evaluate isPal(s[1:-1]). Keep in mind, that s[1:-1] is now "bcb". So run isPal("bcb").
    1. len("bcb") is 3 so go to else.
    2. s[0] == s[-1] is True. Evaluate isPal(s[1:-1]) where s[1:-1] now is "c".
      1. len(s) is 1, therefore: return True
    3. isPal(s[1:-1]) returned True so s[0] == s[-1] and isPal(s[1:-1]) is True. Return True.
  8. isPal(s[1:-1]) returned True so s[0] == s[-1] and isPal(s[1:-1]) is True.
  9. isPal(toChars(s)) returns True: You have a palindrome!

Hope this makes it clearer for you.

EDIT Step 6 does always come before Step 7 because Python explicitly goes from left to right in logical expressions, see here. If this does not happen, your interpreter is broken.

user_84080800
Related