A First Taste of Algorithms

Chapter 4: Recursion That Remembers

✦ ✦ ✦

In which an honest procedure is caught wasting its life, and a wound from Chapter 2 is healed

The staircase

A staircase has n steps. You climb it in hops of one step or two, as you please. Question: how many different ways are there to climb it? (Two ways are different if the sequence of hops differs: 1-then-2 is not the same as 2-then-1.)

Small cases by hand. One step: one way. Two steps: two ways (1+1, or 2). Three steps: 1+1+1, 1+2, 2+1 — three ways. Four steps: enumerate carefully — five ways.

1, 2, 3, 5… Before conjecturing from the pattern, derive the law, Chapter 3 style. Stand at the bottom of n steps and look at your first decision. It is a hop of 1 or a hop of 2 — there is no third kind — and the two choices lead to different futures that can never produce the same climb. Hop 1, and what remains is the staircase problem for n − 1. Hop 2, and it is the problem for n − 2. So:

ways(n) = ways(n − 1) + ways(n − 2), with the floor ways(1) = 1, ways(2) = 2.

A recursion that calls itself twice, on two different smaller cases. Chapter 3’s two rescue conditions hold — strictly downward, solid floor — so the procedure is correct, by the staircase of induction (on an actual staircase, for once). The sequence it generates — 1, 2, 3, 5, 8, 13, 21, 34 — is one of the most famous in mathematics: the Fibonacci numbers, which have a habit of appearing wherever something grows by combining its two most recent pasts. You met some of its members in Chapter 1’s sorted list; now you know what they were doing there.

Correctness settled. Now the second question, and this time the answer is a scandal.

The procedure that forgets

Run the recursion in your head for ways(6) and draw the tree of calls, Chapter 3 style. The top box, ways(6), opens into ways(5) and ways(4). The ways(5) box opens into ways(4) and ways(3). Stop right there — ways(4) appears twice. Keep drawing and count appearances: ways(3) is computed three times, ways(2) five times, ways(1) three times. The full tree for ways(6) contains fifteen boxes to answer what is really six questions.

Figure 4.1 — The amnesiac call tree for ways(6): same shade, same question — fifteen boxes for six questions.

Nothing is wrong. Every box computes a true answer by a valid method. But the procedure has no memory: each time it needs ways(4), it rebuilds the entire ways(4) sub-tree from nothing, like a scholar who burns each page upon finishing it and re-derives the page whenever it’s cited. And the waste compounds on itself: the tree for n contains the whole tree for n − 1 and the whole tree for n − 2, so the call count grows by the staircase’s own law — the cost of computing Fibonacci numbers is itself Fibonacci, which grows like the exponential wall of Chapter 3. In Lab 4 you will count the calls: ways(30), a number you could extend with a pencil in a minute, costs the amnesiac recursion about 1.7 million calls. At n = 50 the pencil still needs its minute; the recursion needs twenty-five billion calls — an hour or more of a modern laptop’s full attention, spent re-answering fifty questions.

Here is the diagnosis to hold on to, because it locates the exponential’s weak point. Hanoi’s 2ⁿ − 1 was a wall of necessary work — the Diamond of Chapter 3 proved every move unavoidable. The staircase’s exponential is a wall of repetition: only n distinct questions exist, asked exponentially many times. A wall made of the same brick photocopied is a wall made of paper.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses