Nib asked for
Remember What You Computed
If you store each subproblem's answer the first time you compute it, every distinct subproblem is solved only once, and the exponential blowup shrinks to linear work.
4 steps, drawn by Nib. Read it here, or watch him draw it. Updated .
1the notebook
Page 2 showed the waste: naive fib(n) recomputes fib(n-2), fib(n-3) and the rest again and again, even though there are only n+1 distinct questions. The fix is a notebook. Before doing any work, ask whether you've already written down the answer to this exact question.
The waste is repeating questions you already answered; a notebook stops the repeats.
a common mix-upFibonacci is slow because the numbers get big; really it is slow because the same calls repeat.
2three moves
The change to the code is small. Create an empty dictionary. At the start of fib(n), if n is in the dictionary, return the stored value immediately. Otherwise compute it as before, store it under n, then return it. The recursion itself is untouched; it just gains a lookup at the front and a save at the back.
Check the notebook first; if missing, compute, save, return.
The first time fib(5) is asked, is it in the notebook? What about the second time?
Show the answer
No the first time, so it is computed and saved; yes the second time, so it returns instantly.
3tree to line
Now trace fib(5). It calls fib(4), which calls fib(3), and so on down to the base cases, computing and saving as the calls return. When fib(5) later asks for fib(3), the answer is already stored, so that whole branch vanishes. The tree that once sprawled collapses into a single chain with quick lookups hanging off it.
Repeated branches are replaced by one-step lookups, so the tree collapses.
a common mix-upMemoization makes each call faster; actually it removes most calls entirely.
4linear vs explosion
Count the work. There are only n+1 distinct questions, fib(0) through fib(n). Each is computed in full exactly once, and that computation does a constant amount of work (one addition plus a few lookups), since its two sub-answers are either just computed or already stored. So total work grows in proportion to n, roughly 1.6^n calls for naive Fibonacci down to about n.
n+1 distinct questions, each solved once, means work proportional to n.
If you ask for fib(40) with memoization, roughly how many times is fib(20) fully computed?
Show the answer
Once; every later request for it is a lookup.
The lesson: count your distinct questions, and make sure you answer each only once. That single habit is the heart of dynamic programming.