Class 12

Recursion

Objectives for today

Define recursion, base case, and recursive case
Identify the base case and recursive case of a recursively-defined problem
Write a recursive function to solve a computational problem
Implement recursion with pending operations

Tower of Hanoi

Tower of Hanoi is a classic puzzle in which you need to transfer a set of discs from one pole to another pole using a spare pole. It has three simple rules:

Only move one disc at a time
Only the top-most disc on a pole can be moved and it must be placed on the top of another pole
A disc can’t be placed on top of a smaller disc

Try playing the game here!

How can we solve this problem? There is definitely some iteration here, but the iterative tools we have seen (for and while loops) might be hard to use at first glance. With problems like this, it’s a good idea to think about:

Can you break the problem into smaller pieces?
After breaking up the problem into smaller pieces, how can you use solutions to those smaller problems to build up the solution to your larger problem?

Approaching the Tower of Hanoi problem

Let’s break up our problem into smaller pieces. The smallest piece (or problem “size”) is a single disk. And we know how to solve that! Just move the disk over to another pole.

If we currently have \(n\) disks, we can move the top \((n-1)\) disks over (assuming we know how to do that), displace the bottom disk to the remaining empty pole, and then displace the top \((n-1)\) disks again on top of the bottom disk.

The main thing to focus on is the fact that we are going to use our solution to the smaller problem in order to solve our current problem.

An example: `factorial`

Iterative approach

As a starting example consider computing the factorial, e.g, \(n!\). A natural iterative solution is below.

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Recursive approach

A recursive algorithm is defined in terms of solutions to smaller versions of the same problem. A recursive function (which implements a recursive algorithm) calls itself to solve a smaller version of the problem.

Let’s think about solving factorial recursively. Can we expression the factorial computation in terms of the solution to a smaller version of the same problem.

5! = 5 * 4 * 3 * 2 * 1
5! = 5 * 4!

A first attempt at a recursive factorial function:

def factorial(n):
    return n * factorial(n-1)

Let’s visualize the call stack:

5 * factorial(4)
    |
    4 * factorial(3)
        |
        3 * factorial(2)
            |
            2 * factorial(1)
                |
                1 * factorial(0)
                    |
                    0 * factorial(-1)
                        |
                        ...

So when will this end? Never! At some point we need to terminate the recursion. We call that the base case. The base case and the recursive relationship are the two key elements of any recursive algorithm.

For factorial, we know that factorial(1) == 1 (and factorial(0) == 1) so:

def factorial(n):
    if n <= 1:
        return 1
    else:
        return n * factorial(n-1)

Here we see the typical structure of a recursive function: First we check if we are at the base case(s), if so return the result directly. If not, we invoke the function recursively on a sub-problem.

Clearly this works. But why? Doesn’t each call to factorial overwrite n? No. To help us understand what happens when we call a function (and what we mean by the call stack) let’s use Python Tutor on our factorial function. Whenever we invoke a function we create a new “frame” on the “call stack” that contains the arguments (local variables and other state in the function). That is n in each recursive call is a different variable. Thus we don’t “overwrite” the parameters when we repeatedly invoke our function.

Limits on the number of recursive calls

Python has a limit on the height of the call stack (that we will encounter if we ever end up with “infinite” recursion). Depending on how many recursive calls you make, e.g. factorial(1000), you may hit that limit triggering a RecursionError (even without infinite recursion). You can increase the limit with a function in the sys module, like shown below, thus enabling us to successfully compute very “deep” recursive functions, e.g., factorial of very large numbers.

import sys
sys.setrecursionlimit(10000)

How to Write a Recursive Function

We employ a 4 step process:

Define the function header, including the parameters
Define the recursive case
- Assume your function works as intended, but only on smaller instances of the problem. How would you implement your solution?
- The recursive problem should get “smaller” (or it will never finish!).
Define the base case
- What is the smallest (or simplest) problem? It should have a direct (i.e. non-recursive) solution.
Put it all together
- First, check for the base and return (or do) something specific.
- If the computation hasn’t reached the base case, compute the solution using the recursive definition and return the result.

Recursion has a similar feel to “induction” in mathematics:

Prove the statement for the first number, or base case
Assume the statement works for an arbitrary number or input
Prove that the given statement for one number implies the statement is true for next number
Therefore it must work for all values!

Let’s use this process to recursively reverse a string (check it out in Python Tutor):

Define the function header, including the parameters
```
def reverse(a_string)
```
Define the recursive case

Assume we have a working reverse function that can only be called on smaller strings. To reverse a string:
1. Remove the first character
2. Reverse the remaining characters
3. Append that first character to the end
Define the base case

The reverse of the empty string is just the empty string.

Put it all together

def reverse(a_string):
    if len(a_string) == 0:
        return ""
    else:
        return reverse(a_string[1:]) + a_string[0]

A note about slicing

An implementation note … Why doesn’t a_string[1:] produce an index error when a_string is a single letter (e.g. "e"[1:])? Slicing has the nice property that slicing beyond the end of the string evaluates to the empty string, e.g.

"e"[1:]

''

However, indexing a single value (not slicing) beyond the end of a string (or list) will produce an error, e.g.

"e"[1]

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[2], line 1
----> 1 "e"[1]

IndexError: string index out of range

How do I make my problem smaller?

The recursive case expresses the solution of our problem in terms of smaller version of the same problem. But how do we make our problem “smaller”? While, there is no “one” way to make the problem smaller, we have seen several common patterns that we can use as we implement our recursive functions:

If we are working with numbers, e.g., “lengths” or “levels”, we can subtract 1, divide by 2 or otherwise make the number smaller
If working with sequences (e.g., strings or lists), which are indexable, we can split the input into the first (or last) element and the “rest” of the string or list with slicing. For example, a_list[1:] would produce a smaller list by “dropping” the first element.

What happens if we don’t make our problem smaller? The function never makes progress towards the base case, recursing infinitely (or still it hits the Python recursion limit).

“Pending operations”

Consider the following code. What is this code doing? What, for example, is the output of the call go_back(3)?

def go_back(n):
    if n == 0:
        print("Stop")
    else:
        print("Go", n)
        go_back(n - 1)
        print("Back", n)

The line print("Back", n) is an example of a “pending operation”. A pending operation gets performed after a/the recursive call, i.e., when control continues after the recursive call. Check this code out in Python Tutor. Pending operations can be a powerful tool when performing operations as a recursive function “unwinds” (i.e., after the base case has been reached).

Exercise: determining if a word is a palindrome

A palindrome is a word that appears the same when read forwards or backwards. Here are some examples:

aha
noon
kayak
madam
rotator
racecar

Here is a possible method which uses a for loop to determine if a word is a palindrome:

def is_palindrome_loop(word):
    """
    Determines if a word is a palindrome.

    Args:
        word: word to check (str)
    Returns:
        True if the input word is a palindrome, False otherwise
    """
    for i in range(len(word) // 2):
        if word[i] != word[-i - 1]:
            return False
    return True

Write a recursive function to determine if an input string is a palindrome.

Possible solution

def is_palindrome_recursive(word):
    """
    Determines if a word is a palindrome.

    Args:
        word: word to check (str)
    Returns:
        True if the input word is a palindrome, False otherwise
    """
    if len(word) < 2:
        return True
    if word[0] != word[-1]:
        return False
    return is_palindrome_recursive(word[1:len(word) - 1])

Challenge: can you extend this to handle palindrome phrases in which punctuation and spaces are ignored? Palindrome phrases (the function should return True) would include:

A Toyota
If I had a hi-fi,
UFO tofu
Never odd or even.
A man, a plan, a canal - Panama!

Hint: use the string replace method to remove punctuation (i.e. replace punctuation characters with an empty string ''). The only punctuation we have in the examples above are ,.-! but you can generalize this by using string.punctuation from the string module.