What is dynamic programming, really? (for a curious adult who has seen a little code but never studied algorithms). Cover, in this order: What does it mean for a function to call itself?; Why does the obvious Fibonacci recursion explode?; What if you remember each answer the first time?; Can you skip the recursion and fill in a table instead?; What makes a problem fit this trick?; How do you use it on a brand-new problem, like fewest coins? — page 2: Why Fibonacci Explodes

Nib asked for

Why Fibonacci Explodes

the short answer

Naive recursive Fibonacci keeps recomputing the same smaller values, so the number of calls grows exponentially even though only a handful of distinct questions exist.

5 steps, drawn by Nib. Read it here, or watch him draw it. Updated 16 Oct 2026.

1the recursion

Fibonacci numbers start 0, 1, and each next number is the sum of the previous two. That rule translates directly into a recursive function: fib(n) returns n when n is 0 or 1 (the base cases), and otherwise returns fib(n-1) + fib(n-2). It reads almost exactly like the definition, which is why it feels like the obvious way to write it.

The obvious code is just the definition: fib(n) = fib(n-1) + fib(n-2), with fib(0)=0 and fib(1)=1.

check yourself

What does fib(4) return, given fib(0)=0 and fib(1)=1?

Show the answer

3, since the sequence runs 0, 1, 1, 2, 3.

2the call tree

Now trace fib(5) as a tree. fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). Each box splits into two boxes below it until you hit 0 or 1. Draw it out and the tree is wide and bushy, far bigger than the small number 5 suggests.

Every call branches into two more calls, so the calls form a tree that widens fast.

3the repeats

Look at the tree for repeats. fib(3) appears twice, fib(2) appears three times, and fib(1) appears five times. Each repeat does the complete work from scratch, including all the calls beneath it, because the function has no memory of having answered that question a moment ago.

The tree contains the same subproblems again and again, and each copy is solved from scratch.

a common mix-upPeople assume each call in the tree is genuinely new work. In fact most boxes are exact duplicates of boxes elsewhere in the tree.

4counting calls

Count the calls as n grows. fib(5) makes 15 calls in total, fib(10) makes 177, fib(20) makes 21,891, and fib(30) makes over 2.6 million. Roughly, each step up in n multiplies the work by about 1.6. Growth by a constant factor per step is exponential: the count doubles about every one or two steps, so modest inputs become hopeless.

Total calls grow exponentially: fib(30) already needs over 2.6 million calls.

check yourself

If going from n to n+1 multiplies the calls by about 1.6, roughly how do the calls for fib(40) compare to fib(30)?

Show the answer

About 1.6 to the tenth power, roughly 100 times more, so hundreds of millions of calls.

5the surprise

Here is the surprise. Across that whole giant tree, only six different questions are ever asked for fib(5): fib(0) through fib(5). For fib(30) there are just 31 distinct questions, yet millions of calls. The explosion is not because the problem is hard. It is because the same few answers are recomputed over and over.

There are only n+1 distinct subproblems, but exponentially many calls to them.

a common mix-upExponential time does not mean the problem itself is inherently hard; here it means the method is wasteful, since the distinct work is tiny.

The blowup comes from forgetting: only a few distinct answers exist, yet we recompute them endlessly. Next page, we fix that by remembering each answer the first time.