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() ⋮

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))

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.

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.

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} \]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)

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.

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`

.

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)`

.

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`

.

How `factorial(3)`

ends up returning 6:

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.

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

We want a function `reverse`

so that `reverse("time") == "emit"`

.

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.

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: ???

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.

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

, all I have to do it put the `"e"`

at the start and I have the correct result.

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)

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)

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.

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

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'

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\).

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"`

.

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`

.

If our recursive function works, we assume we can turn `"ice"`

into `"i c e"`

`"n i c e"`

Yes: we can prepend the first character (`"n"`

) and a space.

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..

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.

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.

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 '

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.

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"`

.

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)

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'

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.

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.

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 |

But why bother?

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

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.

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.