The recursion that never finished

Ravi writes a function to count the ways to climb a staircase of n steps, taking one or two steps at a time. It is four lines and obviously correct:

ways(n):
    if n <= 1: return 1
    return ways(n - 1) + ways(n - 2)

It answers ways(10) instantly. It answers ways(30) after a pause. He runs ways(50) before lunch and it is still running when he gets back.

Nothing is broken. The code is correct. It is simply doing an enormous amount of work, and all of it is work it has already done.

Where the time goes

Draw the calls for ways(5):

ways(5) -> ways(4) + ways(3)
ways(4) -> ways(3) + ways(2)
ways(3) -> ways(2) + ways(1)

ways(3) is computed twice. ways(2) three times. For ways(50) the function calls itself about twenty-five billion times, and there are only fifty different questions it could possibly be asked.

Each step up adds about 60% more work, which is what exponential means in practice.

The fix, in one sentence

There are only fifty distinct questions. Answer each once, write the answer down, and look it up the next time.

That is the whole of dynamic programming. Everything else in this course is detail about how to write the answers down and in what order.