A problem inside a problem

The last chapter ended with a folder of drafts. The size of a folder is the sizes of its files plus the sizes of the folders inside it, and those have folders of their own, and nobody can say in advance how many floors down it goes. Nested loops are helpless here: every floor needs a loop of its own. The hint is hidden in the problem itself. To find the size of a folder, you need the sizes of smaller folders, and that is the same problem, only smaller.

We’ll come back to the folders in the middle of the chapter, once we’ve learned to use that hint. First comes a brain-teaser with a legend: you’ll solve it by hand, then with three lines of code. After that a workshop opens where the same three lines draw trees, snowflakes and triangles made of triangles. It all began with a toy sold in Paris in 1883.

Paris, 1883. A legend in a box

How long the world has left depends on the number of moves for 64 discs. We’ll get to that number, but first, a small tower.

By hand first

Move a tower of three discs from peg A to peg C. Tap a peg to pick up its top disc, then tap another peg to put the disc down. The counter compares your moves with the smallest possible number.

Three discs take seven moves. Four are harder, and with five it’s easy to get lost. Before you read on, place a bet.

Take a tower of four discs and keep your eye on the biggest one. At some point it has to move from A to C. At that moment nothing lies on top of it, and nothing lies on C, or it couldn’t go there. So the three smaller discs must all be on B, the only peg left, and they must form a proper tower. The plan writes itself:

1. move the tower of the top three discs from A to B (C serves as the spare);
2. move the biggest disc from A to C;
3. move the tower of three discs from B to C (now A is the spare).

The first and third steps are the same problem, only with three discs instead of four. And how do you move three? The same way: two onto the spare, the big one into place, the two back on top of it. Two: one onto the spare, the second into place, the first on top. A single disc takes a single move, no plan required. Turn on “Solution” above and watch the plan next to the tower: it grows deeper and then folds back up.

Three lines

The plan goes into Python almost word for word. The function hanoi(n, source, target, spare) moves a tower of n discs from peg source to peg target, using spare as the spare peg, and prints every move.

The function calls itself. This technique is called recursion, from the Latin recurrere, “to run back, to return.” Run the cell, then press “Moves from the cell” in the game above, and the tower will replay the moves of your program. Change 3 to 5, or to 8 as in Lucas’s box, and check again.

A recursive function always has two parts. The first is the base case: a problem so small that it is solved on the spot. Here it is a tower of zero discs, which needs no moves at all. The second is the step: the problem is reduced to smaller ones of the same kind. Here a tower of $n$ discs is reduced to two towers of $n - 1$. Every call makes $n$ one smaller, so sooner or later it reaches zero and the recursion stops.

Press “Steps” under the program. The frames column shows the calls piling up: hanoi(3, …) calls hanoi(2, …), which calls hanoi(1, …), which calls hanoi(0, …), which returns at once. Each frame has its own n, source, target and spare, so the calls never get confused about who is moving what where.

How many moves

Let $T(n)$ be the number of moves our function makes for $n$ discs. The base case makes no moves: $T(0) = 0$. The step moves two smaller towers and makes one move between them: $T(n) = 2T(n-1) + 1$. So $T(1) = 1$, $T(2) = 3$, $T(3) = 7$, $T(4) = 15$, each one less than a power of two.

The proof works like this: check the smallest case, and for a bigger one use the fact that everything is already proved for the smaller one. This is mathematical induction, which the math course explains with falling dominoes. Induction proves a statement for $n$ by leaning on $n - 1$; recursion computes an answer for $n$ by leaning on $n - 1$. It is one idea said twice, and in both cases nothing works without the base.

All that’s left is to work out how long the world has.

About 585 billion years. The world of Lucas’s legend is in no danger: even if the Brahmins had started at the Big Bang, nearly all their work would still lie ahead. A computer making a billion moves a second would need about 585 years: the same digits, minus the billions. The number $2^n - 1$ grows so fast that no speed can catch up with it; that is the subject of Chapter 13.

How Python keeps its place

In Chapter 5 we saw that every call of a function gets its own frame, a workbench with its own variables, and that the frames pile up into the call stack. We also saw there why EDSAC subroutines couldn’t call themselves: the return address was kept in a single place, and a second call wiped out the first one’s. In Python every frame holds its own return address, so a function can call itself again and again, until it hits a limit we’ll meet below, and every call returns to the place it was called from.

Here is the stack at work on the most classic recursive function there is. The factorial $n!$ is the product of the numbers from 1 to $n$: $5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$. But $5! = 5 \cdot 4!$, and in general $n! = n \cdot (n-1)!$, which is a ready-made recursive step. The base case is $0! = 1$ (that is the convention, and a handy one: the product of an empty set of numbers is one).

Press “Steps” and follow what happens to factorial(5). It can’t return an answer right away: it needs factorial(4), so it waits. That one waits for factorial(3), and so on down to factorial(0), which returns 1 without calling anything. Now the pile starts to come apart: factorial(1) gets 1 and returns $1 \cdot 1$, factorial(2) gets 1 and returns 2, and so on up to 120. Recursion works in two passes: on the way down it puts the multiplications off, and on the way back up it does them.

Trust the recursion

Following a recursion step by step is worth doing once or twice. Writing recursion that way is hopeless: a Tower of Hanoi of eight discs makes 511 calls, and there is no point in keeping them all in your head. Experienced programmers reason differently. When you write the step, assume the function already works on smaller problems, and think only about how to build your answer out of theirs. People call this the leap of faith, but no faith is involved, only induction: if the base case is right, and the step correctly builds an answer from correct smaller answers, the function is right for every $n$.

Try this way of thinking on three small functions. The sum of a list is its first item plus the sum of the rest. A string is a palindrome if its first and last letters match and the middle is a palindrome. The number of digits in a number is one plus the number of digits in that number without its last digit.

Each function holds two thoughts: what to do with the smallest problem, and how to reduce a big one to a smaller one. How total will manage to add up the rest is none of your concern: that is its own job, on a smaller problem. Test yourself.

Bottomless

The stairs above, in “without the base case” mode, show what happens when the base case never comes. Or you can run this.

The countdown ran past zero, went negative and stopped at −991 with the error RecursionError: maximum recursion depth exceeded. Every frame takes memory, and the memory for the stack is not endless. If Python didn’t watch the depth, an endless recursion would bring the whole program down, so Python allows about a thousand nested calls and on the next one stops the program with an error you can make sense of. The function sys.getrecursionlimit shows the limit; it also counts the few frames already taken before the first call. A crash like this is called a stack overflow, and the best-known question-and-answer site for programmers is named after it.

You can raise the limit with sys.setrecursionlimit, but that treats the symptom. The depth of our recursion equals $n$: the factorial of a thousand hits the limit, though it takes no time at all to compute. Problems in which the recursion goes down thousands of floors are better solved with a loop or with a shallower recursion, say one that splits the problem in half instead of into “one and the rest.” That idea is what Chapter 21 is built on, and it also solves the first task of this chapter.

The workshop: the tree from Chapter 0

In Chapter 0 a turtle drew a tree from a dozen lines, and we promised to explain how it did it. Here is the same function; this time you can read every line of it.

A branch is a trunk with two smaller branches growing on it. The definition refers to itself, like the Tower of Hanoi, and the code follows the definition. One detail holds the whole tree together: the function returns the turtle to the spot where it found it, facing the same way. A turn of 25° to the left, 50° to the right and 25° to the left again adds up to nothing, and t.back(length) walks the turtle back down the trunk. Thanks to this, while drawing the left subtree, you don’t have to think about where the turtle will end up: it will be where it was before the call. This is the same trust in recursion, only in geometry. Delete the line t.back(length), run the cell again and compare the trees.

Now count the branches. At depth 9 there is one branch, at depth 8 there are two, at depth 7 four, and so on, down to 256 at depth 1: $1 + 2 + 4 + \dots + 256 = 2^9 - 1 = 511$ in all. Once again $2^n - 1$, and not by chance: the call tree of branch has the same shape as the call tree of hanoi, except that each call draws a branch instead of moving a disc.

Press “How recursion draws it” in the workshop with the tree selected. You might expect the turtle to work in tiers: first all the thick branches, then the thin ones. Instead it heads down the leftmost branch all the way to its tip, steps back once, draws the neighboring tip, and in this way makes its way around the whole tree. This is the order of a depth-first search, and the stack dictates it: until a call has finished, its neighbors to the right wait their turn.

The Koch snowflake

In 1904 the Swedish mathematician Helge von Koch described a curve made of nothing but kinks. The rule: take a segment, divide it into three parts and replace the middle one with two sides of an equilateral triangle, which gives a broken line of four segments. Do the same with each of them, and so on without end. Three such curves on the sides of a triangle make a snowflake.

There isn’t a single loop inside koch, only four calls and three turns. Each level replaces a segment with four segments a third as long, so the length of the curve is multiplied by $\frac43$. At depth 4 the snowflake has $3 \cdot 4^4 = 768$ segments, and its perimeter is $\left(\frac43\right)^4 \approx 3.2$ times that of the original triangle. Keep going forever, and the perimeter grows without bound while the area stays finite: the snowflake never gets outside the circle drawn around the triangle. Shapes like this, which reveal new detail at any magnification, are called fractals. The math course has a chapter about them, which also answers the question of how long the coast of Britain is.

The Sierpiński triangle

One more fractal: a triangle made of three triangles half its size, each of them made of three smaller ones still. The Polish mathematician Wacław Sierpiński described it in 1915. The recursion here can be read straight off the definition: to draw a triangle of depth $d$ is to draw three triangles of depth $d - 1$ in its corners.

The number $0.866$ is $\frac{\sqrt3}{2}$, the height of an equilateral triangle with side 1. At depth 5 there are $3^5 = 243$ filled triangles. The same pattern appears in Pascal’s triangle if you color its odd numbers, and in the last task of this chapter you’ll build it out of lines of asterisks.

Back to the folders

We now have all we need to answer the last telegram of the previous chapter. The size of a folder is the sum over everything inside it: a file contributes its size, and a folder inside contributes its own size, worked out by the same function.

Here the base case doesn’t get a line of its own at the top of the function: a folder that holds only files makes no recursive calls, and that is where the descent ends. The depth of the recursion equals the depth to which the folders are nested, whatever it is. The nested loops of the last chapter gave up on the third floor, while this function goes down to the third or the thirtieth with the same calm.

The same technique prints a folder’s table of contents, the way the tree command does in a terminal. The indent grows with the depth, so it is passed along as a parameter.

Any nested data is walked the same way. The JSON from the last chapter is dictionaries and lists nested inside one another to any depth. So is a list that may contain lists. A function that walks such a structure nearly always looks the same: go through the items; if an item is simple, handle it; if it is a structure itself, call yourself on it.

Every Morse code

Recursion can do more than walk through what already exists: it can also list every possibility. Back to Morse code. How many codes of $n$ signals are there? A code of $n$ signals is a code of $n - 1$ signals with a dot or a dash added at the end. So all the codes of length $n$ come from all the codes of length $n - 1$: a problem inside a problem once again.

For $n$ signals there are $2^n$ codes: each new signal doubles the number of choices. One, two, three and four signals together give $2 + 4 + 8 + 16 = 30$ codes. That is enough for all 26 letters of the Morse table from the last chapter, with four codes to spare; in German they stand for Ä, Ö, Ü and CH. The ten digits had to make do with five signals each. The Russian telegraph alphabet of 1856 was less lucky: it had 32 letters, the short codes ran out, and two of its letters got five signals.

The subtlest place here is the base case. The number of codes of length 0 is not zero: there is one, the empty string. Return an empty list instead, and the loop on the next level has nothing to go through, so every answer comes out empty. The base case is where mistakes happen most often, and you check it the way you check the base of an induction: on the smallest input, the answer must be right on its own.

Permutations, all the ways of putting the letters of a word in a row, are built in a similar way. Any letter can come first, followed by any permutation of the rest. Three different letters have $3 \cdot 2 \cdot 1 = 6$ permutations, and $n$ different letters have $n!$, the factorial from the section on the stack. You’ll write them yourself in the tasks.

Recursion or a loop

The factorial can be computed with a loop too, and it is even simpler that way.

A loop doesn’t run into the depth limit and doesn’t spend memory on thousands of frames. For problems that come down to the same problem “one smaller” in a straight chain (the factorial, the sum of a list, a countdown), a loop is usually the better choice. Recursion wins where the problem branches: the Tower of Hanoi, trees, folders, going through all the possibilities. These can be written with a loop as well, but then you have to keep the pile of unfinished business yourself, which recursion gets from the call stack for free.

There is a third case: branching recursion that does the same work over and over. In the Fibonacci numbers, 0, 1, 1, 2, 3, 5, 8, 13, …, each number is the sum of the two before it, and the definition begs to be turned into code. The math course tells their whole story.

Every time $n$ grows by five, the time grows more than tenfold. The call tree shows why.

In the tree of fib(5), the call fib(3) appears twice and fib(2) three times, and every time everything is computed from scratch. That makes 15 calls to get the number 5. For fib(30) there are 2,692,537 calls, for fib(40) 331,160,281, and among them only 41 different arguments. Each time $n$ goes up by one, the tree grows about 1.6 times (that is the golden ratio), and every five steps it grows elevenfold.

This is the trouble the Tower of Hanoi had, except that here it is pointless: the Brahmins need every one of their $2^{64} - 1$ moves, while here nearly all the work is repetition. How to estimate the running time of such programs in advance is the subject of Chapter 13. How to remember what has already been computed, and get by with forty-one computations instead of hundreds of millions of calls, is Chapter 22.

Tasks

Five tasks. In each, think about two things first: which case is the simplest, and how to reduce the problem to a smaller one. The tests call your functions and compare what they return.

What next

Think back to the functions that walked through folders and nested lists. folder_size adds up sizes, show prints names, nested_sum adds up numbers, flatten collects them into a list. They share one skeleton: go through the items, handle a simple one, hand a compound one to the same function. Only the filling differs: what to do with a simple item. Writing the skeleton once and passing in the filling separately is beyond us so far, because we have only ever passed functions numbers, strings and lists. What if we passed a function another function? Python allows it, and a whole way of writing programs grows out of that. It is the subject of Chapter 10.