Memoization: stop solving the same problem twice

01Why it matters

The same question, asked hundreds of times

The Fibonacci numbers are defined by themselves: $F(n) = F(n-1) + F(n-2)$ , starting from $F(0) = 0$ and $F(1) = 1$ . Code that follows the definition word for word is correct, short, and astonishingly slow: computing $F(40)$ makes over 300 million calls.

It isn't slow because addition is slow. It is slow because it asks the same questions again and again. Memoization fixes that with one idea: write each answer down the first time, and look it up after that. It is the first step towards dynamic programming.

02Key parts

The pieces you will see

call: One run of fib(k). Each call that isn't a base case makes two more calls.
call stack: The calls still waiting for an answer, deepest on top.
memo: A table of answers already found: memo[k] holds fib(k) once it is known.
memo hit: A call answered by looking in the memo instead of recursing.

03See it work

First, without a memo

Watch plain recursion compute fib(6) and keep an eye on the calls row: fib(2) is computed 5 times and fib(1) 8 times.

25 calls for fib(6). Each extra n multiplies the calls by about 1.6.

Now the same function with a memo. The first time fib(k) finishes, its answer goes into memo[k]; every later call to fib(k) returns it at once.

11 calls for fib(6): each value is computed once and looked up after that.

04Predict

Your turn: hit or miss?

Predict whether each call can be answered from the memo or has to recurse.

Make 5 predictions: step forward and answer each question before the next step plays.

05Try it

Turn it around: fill the table bottom-up

Instead of recursing from the top and remembering on the way back, you can fill the table from the bottom: dp[0], dp[1], then each dp[i] from the two before it. Same answers, no recursion, no call stack. This is dynamic programming: choose an order in which every value's inputs are already filled in.

Raise n to 15 and compare: the table needs 14 additions, while plain recursion would make 1,973 calls.

06Check yourself

Check yourself

Question 1 of 5
Why is plain recursive Fibonacci slow?
Your answer comes back in Review in a few days, so it sticks.
Question 2 of 5
With a memo, how many distinct values does fib(30) compute?
Question 3 of 5
What does the bottom-up version need that the top-down version works out for itself?
Question 4 of 5
Would adding a memo speed up merge sort?
Question 5 of 5
Someone writes fib(n) so that every call begins with memo = {}. How fast is it?

07Explain it back

Say it in your own words

Why is plain recursive Fibonacci so slow, and how does a memo make it fast?

08Recap

What to remember

Memoization = recursion + a table of answers. It turns repeated work into look-ups.
Cost becomes the number of distinct subproblems times the work per subproblem: for Fibonacci, O(n) instead of O(1.6ⁿ).
Bottom-up dynamic programming fills the same table in a chosen order, without recursion.
Next: coin change, knapsack and edit distance are all "find the subproblems, then fill the table".