Recursion

Recursion

We have seen that it's possible for functions to call other functions, like you probably did in roll_dice in the exercise:

def sum_two_dice():
    ⋮
    return total

def roll_dice(num):
    ⋮
    r = sum_two_dice()
    ⋮

Recursion

And we know about local variables. We know that a variable like num in one function call is unrealated to the identically-named variable in another.

def roll_dice(num):
    ⋮
    r = sum_two_dice()
    ⋮
def draw_histogram(counts):
    ⋮
    num = counts[i]
    ⋮
img = draw_histogram(roll_dice(1000))

Recursion

Because of this, it turns out that it's possible for a function to call itself. Any function that calls itself is known as recursive.

Recursion

For example, to implement merge sort as described in the last slide deck involved breaking up the list into left and right halves and then using merge sort itself to sort either half.

Implementing that algorithm (which I wouldn't ask you to do in this course) would require a mergesort function that called mergesort on a smaller list as part of its implementation.

Recursion

Consider the factorial function which can be defined:

\[ n! = 1\times 2\times\cdots\times n\,. \]

But it can equally well be defined as:

\[ n! = \begin{cases} n\times(n-1)! & \text{if \(n > 0\),}\\ 1 & \text{if \(n = 0\).} \end{cases} \]

Recursion

The first definition could be implemented with a for loop, but that's not the topic at hand. The second definition can also be written directly in Python as a recursive function.

def factorial(n):
    """
    Calculate factorial of n.
    """
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

Recursion

This function actually works:

>>> factorial(5)
120

But how?

Hopefully we can agree that factorial(0) will return 1, so the n==0 case is correct.

Recursion

Now let's look at what factorial(1) does when it's called.

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

It calculated 1 * factorial(0). We know that factorial(0) will return 1, so that calculation will return 1*1 == 1.

Recursion

This works because the two function calls are independent. The local variable n doesn't exist in the function factorial. It exists in the call to factorial(1) and another exists in factorial(0).

factorial(1) call

Recursion

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

Then factorial(2) will return 2 * factorial(1) == 2.

And factorial(3) is 3 * factorial(2) == 6.

And factorial(4) is 4 * factorial(3) == 24.

Recursion

How factorial(3) ends up returning 6:

factorial(4) call

Recursion

Basically, our factorial function is correct as long as:

  • it returns the correct thing for n==0;
  • for other n, it correctly uses the recursive result to calculate the result.

Or in other words, we have broken the problem up into separate cases: if the function returns the correct result in each case, it must be correct.

Example: Reversing

Let's solve another problem recursively: reversing a string.

We want a function reverse so that reverse("time") == "emit".

Example: Reversing

In all recursive solutions, we need somewhere for the recursion to stop: a case where we know the result and don't have to make a recursive call. Usually this is going to be the smallest possible value for the argument.

This is the base case: the argument(s) where we don't recurse, but can just return the correct return value easily.

Example: Reversing

For a string, the smallest one is the empty string: "". (Note: not a space, a zero-length string.)

And it's easy enough to reverse it: I'd expect reverse("") to return "", so we can fill in that case easily enough.

def reverse(s):
    if s == "":
        return ""
    else:
        ???

Example: Reversing

The recursive case is any argument values that aren't the base case, where we make a recursive call (to the function itself). In this problem, that will be everything but the empty string.

We need to figure out how to make the problem smaller: something that will move us toward the base case, and would be helpful to get us the result we're trying to produce.

Example: Reversing

For reversing a string, I want reverse("time") to return "emit". The question: is there some string I could reverse that would help me get close to that?

Proposal: if I could reverse everything but the last character, I'd be very close to the result.

i.e. if I had reverse("tim") == "mit", all I have to do it put the "e" at the start and I have the correct result.

Example: Reversing

Or more generally, I can split off the last character with stuff we have seen:

last_char = s[-1]
all_but_last = s[:-1]

Then if I can reverse the one-character-shorter prefix, I'm basically done.

return last_char + reverse(all_but_last)

Example: Reversing

The pieces together:

def reverse(s):
    """
    Return reverse of s.
    """
    if s == "":
        return ""
    else:
        last_char = s[-1]
        all_but_last = s[:-1]
        return last_char + reverse(all_but_last)

Example: Reversing

There were some choices I made there can could have been made differently: I might have noticed that any length 1 string is also its own reverse (i.e. reverse("a") == "a").

Or, I could have picked off the first character instead of the last.

Example: Reversing

Those choices would have led me to different but also perfectly correct recursive function:

def reverse2(s):
    """
    Return reverse of s.
    """
    if len(s) <= 1:
        return s
    else:
        first_char = s[0]
        all_but_first = s[1:]
        return reverse2(all_but_first) + first_char

Working With Recursion

If you want to solve a problem recursively, there's a few general things you have to figure out. Let's do another example.

I want a function spaced_out that takes a string and returns a version of it with spaces between each character. I could do that with a string method, but I want to write my own.

>>> " ".join("hello")
'h e l l o'
>>> spaced_out("hello")
'h e l l o'

Working With Recursion

Step #1: find a smaller sub-problem. We need some way to take a step that can contribute to an overall solution that is a smaller version of this problem. This will be our recursive step.

Often this will be (the relevant interpretation of) the \(n-1\) case: make the problem one unit smaller. e.g. for factorial, we went from n to n-1. For string reversing, we turned a string of length \(n\) into a string of length \(n-1\).

Working With Recursion

For the spacing-out function, one unit smaller could be removing the first or last character. Either would work, and I'm going to remove the first: turn "nice" into "ice".

Working With Recursion

Step #2: use the solution to the sub-problem. Assume we can get a correct result for the recursive step. Can we use that to get the result we're trying to return? [If the answer is no, we probably took the wrong recursive step.]

In the examples, assume we can calculate \((n-1)!\) or get the reverse of s[1:]. Use those to take the last step to \(n!\) or the reverse of s.

Working With Recursion

If our recursive function works, we assume we can turn "ice" into "i c e". Is that useful to build the string "n i c e"?

Yes: we can prepend the first character ("n") and a space.

Working With Recursion

Step #3: find a base case. There will one or two small cases where the recursive method doesn't work: it fails or gives an incorrect result. Generally, look for the (appropriately interpretted) \(n=0\) or \(n=1\) case.

For factorial, \(0! \ne (0-1)!\) because \((-1)!\) isn't defined. For string reversing, we can't examine the first character of a string with length zero..

Working With Recursion

For the string spacing problem, our previous method certainly won't work for length zero strings. We probably want spaced_out("") to return "".

It will be a problem later, but for now, let's have that be our base case: length zero strings.

Working With Recursion

Step #4: put it all together into a recursive implementation.

The overall shape will always be: if we're in the base case return that result, else recurse. For occasional problems, you might have two distinct base cases or something, but that's rare.

Working With Recursion

For the spaced_out function, that would lead us to this implementation:

def spaced_out0(s):
    if s == "":
        return s
    else:
        first = s[0]
        tail = s[1:]
        return first + " " + spaced_out0(tail)

… and it's almost right. There's an extra space.

>>> spaced_out0("nice")
'n i c e '

Debugging Recursion

If a recursive function doesn't return the right results, maybe the base case is wrong, maybe the recursive case is wrong, or maybe we're wrong about how the cases got separated.

The easiest first step: check the base case.

>>> spaced_out0("")
''

That's okay.

Debugging Recursion

Then check one step away from the base case, were we start to see the extra space:

>>> spaced_out0("a")
'a '

The problem is that this string is handled by the base case: spaced_out0("a") returns:

"a" + " " + spaced_out0("") == "a "

I'd like the result in this case to just be "a".

Debugging Recursion

Fundamentally here, the choice of what is in the base case was wrong: strings of length 1 should have been handled separately. For length 0 and 1, we want to return the original string, unchanged.

def spaced_out(s):
    """
    Return a string with spaces between each character.
    """
    if len(s) <= 1:
        return s
    else:
        first = s[0]
        tail = s[1:]
        return first + " " + spaced_out(tail)

Debugging Recursion

It seems to work as expected now:

>>> spaced_out("")
''
>>> spaced_out("a")
'a'
>>> spaced_out("nice")
'n i c e'
>>> spaced_out("seems okay")
's e e m s   o k a y'

Other Examples

Let's try a few more. Some of:

  • Calculating \(a^b\) for positive integer \(b\).
  • Convert an unsigned number to binary.
  • Produce all binary strings length n.
  • Sum the values in a list.
  • Linear search.
  • Quicksort or Merge sort.
  • Count the number of occurrences of a specific value in a list.
  • Map a function over a list.

Why Recursion?

We have seen that recursive definitions are fundamentally a way to replace a loop (with recursive function calls).

We have been taking what we might have thought of as a looping problem, but instead figuring out how to phrase it as a partial solution → full solution recursive step.

Why Recursion?

e.g. in some sense, these are implementations of the same accumulator pattern, roughly the last character goes before the already-reversed part.

def rev(s):
    if s == "":
        return ""
    else:
        c = s[-1]
        res = rev(s[:-1])
        return c + res
 
def rev(s):
    res = ""
    for c in s:
        res = c + res
    return res

Why Recursion?

But why bother?

The answer depends: many programmers probably go for years and never solve a problem recursively.

Why Recursion?

But there are some problems that are just easier or more natural to solve with recursion. e.g. (in my opinion) binary strings ↔ integer conversion; produce all binary strings; merge sort; quicksort; many graph/​tree algorithms.

I'd argue that recognizing the case where recursion makes things easier is one of the markers of a great programmer.

Why Recursion?

Those of you headed down a CS path should eventually get comfortable with recursion.

For the rest of you, it might be a curiosity of this course and nothing more.