Understanding Recursion and Multiple Returns

Question

I'm working my way through the MIT 6.00 class on OpenCourseWare and I'm having a little trouble with the lecture on recursion. I think I understand the basic idea, that you can break some problems down into smaller, repeatable problems. Where I'm having trouble is understanding how this works in the actual code. There is one specific example that I don't quite understand...

def toChars(s):
    import string
    s = string.lower(s)
    ans = ''
    for c in s:
        if c in string.lowercase:
            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])

def isPalindrome(s):
    """Returns True if s is a palindrome and False otherwise"""
    return isPal(toChars(s))

This code is supposed to check if a string is a palindrome or not. I am a little lost on how isPal(s) works. Here's the steps as I'm reading them...

1. Check if s is one character or less, if it is return True.
2. If s has more than one character return a Boolean value (True or False) from the expression comparing the first and last character. So basically check if the first and last letter are the same.
3. AND return the result of the function run again with the first and last letters stripped from the string.

What is confusing me is the return s[0] == s[-1] and isPal(s[1:-1]) bit. I'm not sure I understand what it means to both return True/False based on the first expression AND return the function. Honestly I'm not even sure what returning the function actually means, I'm guessing it just runs the function again, but doesn't actually return any value. I also don't understand how this can actually tell if a string is a palindrome or not. Wouldn't it just keep hitting the second part of return s[0] == s[-1] and isPal(s[1:-1]) until the string, whether it was a palindrome or not, was reduced to 1 or 0 characters? The only thing I can think of is that returning a false value from return s[0] == s[-1] exits the function with a return of false? But I don't feel like that's actually how Python works, at least in my study so far I haven't run into anything saying that returning a False in a function would prevent the second part of the return statement from executing, which would call the function again regardless of whether the first and last letters where the same.

I'm kind of banging my head against the wall at this point, so any insight would be really appreciated!

Answer 1

Perhaps the best way is to go step by step with the values for that line that is confusing you.

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

Assuming the String you're testing for is "ABCDBA", here is the sequence of calls

return s[0] == s[-1] and isPal(s[1:-1]) #evaluate to ("A" == "A" and isPal("BCDB")) - need to go deeper
return s[0] == s[-1] and isPal(s[1:-1]) #evaluate ("B" == "B" and isPal("CD")) - need to go deeper
return s[0] == s[-1] and isPal(s[1:-1]) #returns ("C" == "D")

Note that in the last line we didn't evaluate for isPal because of short-circuiting - we know that False and X where X can be True or False is always False. Read more about that here.

At the last line we're 4 functions deep into isPal. Since the last line doesn't require us evaluate for isPal() again, we start "rising to the surface" back to the original invocation of isPal which was at

def isPalindrome(s):
    """Returns True if s is a palindrome and False otherwise"""
    return isPal(toChars(s))

Answer 2

One clarification which can help you understand what's going on: return ...X and ...Y means: Compute the value of X. If the value is false, return it, otherwise compute the value of Y, and return it.

More info about the short-circuit, lazy behavior (i.e. not evaluating Y if not needed) of the and and or operators in Python: https://docs.python.org/release/2.7/reference/expressions.html#boolean-operations

So that statement doesn't make the function return two values (X and Y), but one value which is the logical AND of X and Y: it's true iff both X and Y are (evaluated to) true.

Also it's worth distinguishing function from function call. There can be many active calls to the same function, with different arguments, local variables etc., so their return values can also be different (as soon as they return). When a function calls itself, that's called recursion. When a function call returns, execution continues in the caller, which can be the same function (but of course a different, upper-level function call) in case of recursion.