Recursion, properly

No problems in this lesson. It exists because everything after it, and both of the hardest units later, assume it.

Why this lesson exists

If you already write recursion comfortably, this will take ten minutes and the drills will still be worth doing. If you do not, this is the most important lesson in the course, because backtracking and dynamic programming are both recursion with extra bookkeeping, and neither is learnable while recursion itself is shaky.

Key idea

Two parts, and only two

A recursive function needs a base case, which answers the smallest input directly, and a recursive case, which reduces a larger input to smaller ones and combines their answers.

That is the whole structure. Most difficulty comes from trying to hold the entire chain of calls in your head, which is neither necessary nor possible past about three levels.

1def total(values, index=0):2    if index == len(values):        # base case: nothing left3        return 04    return values[index] + total(values, index + 1)5 6print(total([3, 1, 4]))

What actually happens

Each call gets its own copy of the local variables, stacked on top of the caller's. When a call returns, its frame is discarded and the caller resumes exactly where it left off.

The depth of that stack is the space cost of a recursion, which is why an O(n) recursion can use O(n) space even when it allocates nothing. Python stops you at a depth around a thousand by default, which is a real constraint on some problems and never an issue on balanced trees.

1import sys2print(sys.getrecursionlimit())3 4def depth_of(n):5    if n == 0:6        return 07    return 1 + depth_of(n - 1)8 9print(depth_of(900))10try:11    depth_of(10000)12except RecursionError:13    print("RecursionError")

Gotcha

Forgetting to return the recursive call

The single most common recursion bug in any language: making the call but not returning what it produced. The function runs, does all the work, throws it away, and returns None.

It is invisible in the code because the recursive line looks busy. If a recursion returns None when it should return a value, check that every path has a return in front of the call.

1def broken(values, index=0):2    if index == len(values):3        return 04    broken(values, index + 1)       # result discarded5    return values[index]6 7def fixed(values, index=0):8    if index == len(values):9        return 010    return values[index] + fixed(values, index + 1)11 12print(broken([3, 1, 4]), fixed([3, 1, 4]))

Predict the output· 5 min

Predict the output: before or after the call

The same recursion prints in two different places. Type both lines of output, each as digits separated by single spaces.

Python

1def down(n):2    if n == 0:3        return4    print(n, end=" ")5    down(n - 1)6 7def up(n):8    if n == 0:9        return10    up(n - 1)11    print(n, end=" ")12 13down(4)14print()15up(4)16print()

Printed output

Code lab· 25 min

Recursion drills

Four small recursions, no trees yet. Write each one recursively even where a loop would be shorter, because the point is the shape. count_down builds a list from n to 1. sum_digits adds the digits of a non-negative integer. is_palindrome checks a string. flatten turns a nested list of lists into a flat list.

solution.py

Tests

print(count_down(4), count_down(0))print(sum_digits(1234), sum_digits(0))print(is_palindrome("racecar"), is_palindrome("abca"), is_palindrome(""))print(flatten([1, [2, [3, 4]], 5]), flatten([]))

Output

Run tests to see output.

Why this lesson exists

What actually happens

Each call gets its own copy of the local variables, stacked on top of the caller's. When a call returns, its frame is discarded and the caller resumes exactly where it left off.

1import sys2print(sys.getrecursionlimit())3 4def depth_of(n):5    if n == 0:6        return 07    return 1 + depth_of(n - 1)8 9print(depth_of(900))10try:11    depth_of(10000)12except RecursionError:13    print("RecursionError")