Solving the Same Thing Over and Over

Last timeSplitting the Work in Half

When a recursion calls itself twice, the two branches ask many of the same questions, and the number of times one small question is asked grows out of control.

A method that looks fine

Here is a problem with a one line answer. How many ways are there to climb a

staircase of $n$ steps, taking either one step or two at a time?

The sentence from lesson one writes itself. The last move was either a single

or a double, so the number of ways to reach step $n$ is the number of ways to

reach step $n - 1$ plus the number of ways to reach step $n - 2$ . There is one

way to stand at the bottom and one way to climb a single step.

Three lines, no loop, provably correct, and the smallest cases cover both

chains as lesson two demands. It also cannot be used.

FIG 1Correct, checkable, and unusable

python

import time
def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)
for n in (10, 20, 30, 35):
    t = time.time()
    r = ways(n)
    print(n, r, round(time.time() - t, 2), "seconds")
print("10 gives 89 in no measurable time")
print("20 gives 10946 in no measurable time")
print("30 gives 1346269 in 0.2 seconds")
print("35 gives 14930352 in 2.4 seconds")
print("50 would take about four days, and 60 about a year and a half")

Nothing in the three lines hints at any of this. The numbers it produces are small enough to hold in a single machine word, the method does nothing but add, and it still takes four days at fifty.

Why: the tree

The difference from everything in the first four lessons is that this

recursion calls itself twice. That changes the shape of what happens from a

chain into a tree.

A chain of calls has one call at each level, so a thousand levels means a

thousand calls. A tree where each call makes two more has one call at the top,

two below it, four below those, and roughly twice as many at each level down.

With $n$ levels that is around $2^n$ calls at the bottom, and the method does

one addition for each of them.

FIG 2The first four levels of the tree for ways(6)

step	level	the calls at this level	how many
1	0	ways(6)	1
2	1	ways(5), ways(4)	2
3	2	ways(4), ways(3), ways(3), ways(2)	4
4	3	ways(3), ways(2), ways(2), ways(1), ways(2), ways(1), ways(1), ways(0)	8
5	4	the remaining calls on 2, 1 and 0	10

5 steps

Read the third level across. The call on four appears once, the call on three twice, the call on two three times already, and it has not finished. Every one of those repeated calls goes on to expand its own entire subtree below it, which is where the cost comes from.

Counting the repeats

The tree is not full of different questions. It is full of the same questions,

and the smaller the question the more often it is asked.

Computing the number of ways for thirty steps involves asking about

twenty nine steps once, twenty eight steps twice, twenty seven steps three

times, and so on, with the counts growing as you go down. By the time it

reaches the smallest cases, which cost nothing to answer, it is asking them

hundreds of thousands of times.

The lesson stops here

5 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents