---
title: "Fibonacci & Memoization"
description: "From naive recursion to bottom-up DP"
source: https://vizlearn.app/algorithms/dp/fibonacci
---

# Fibonacci & Memoization

Memoization is the technique of caching a function's results so repeated calls with the same argument return instantly; the Fibonacci sequence — `fib(n) = fib(n-1) + fib(n-2)`, with `fib(0) = 0` and `fib(1) = 1` — is its canonical demonstration. Plain recursion recomputes subproblems exponentially often; one cache collapses the cost from roughly O(2ⁿ) to O(n).

Picture a clerk computing a subtotal from scratch every single time someone asks, even when they asked five minutes ago. That clerk is naive recursion. Memoization hands the clerk a notebook: compute once, write it down, and from then on answering is just looking it up. Dynamic programming is the discipline of using that notebook on purpose — and this lesson shows the same computation three ways, so you can watch the wasted work appear and then vanish.

## How Memoization Works

**Naive recursion** (the default view) writes the recurrence directly as a function and builds a *recursion tree*. `fib(6)` calls `fib(5)` and `fib(4)`; each splits again, down to the base cases `fib(1)` and `fib(0)`. Nothing is remembered, so an entire subtree like `fib(4)` gets rebuilt from scratch every time it is requested. The clerk has no notebook; every question restarts the whole calculation.

**Top-down memoization** keeps the identical recursion and adds the notebook: a `memo` dictionary. The first time `fib(4)` is computed, the result is stored. Every later request becomes an O(1) lookup — a *cache hit* — and that whole subtree is never expanded again. The tree gets pruned to a thin spine.

**Bottom-up tabulation** throws away the recursion and fills the notebook in order. A table `dp[]` grows left to right: `dp[0] = 0`, `dp[1] = 1`, then each `dp[i] = dp[i-1] + dp[i-2]`. Every cell is written exactly once, reading only the two cells before it. No call stack, no waiting children — by the time you need an answer, you have already written it.

All three agree on the answer; they differ only in whether the fact "once `fib(k)` is known, it never needs computing again" gets exploited. Naive ignores it, memoization exploits it lazily, tabulation exploits it eagerly.

## Fibonacci Step by Step

The default run is **naive recursion with n = 6**, so the target is `fib(6) = 8`.

1. **Call `fib(6)`.** It needs `fib(5) + fib(4)` and recurses into `fib(5)` first.
2. **Drill down the left spine** — `fib(5) → fib(4) → fib(3) → fib(2)` — until it bottoms out at `fib(1) = 1` and `fib(0) = 0`.
3. **Combine upward.** With both children resolved, a `combine` beat does the arithmetic — `fib(2) = 1 + 0 = 1` — and a separate `return` beat commits the value and hands it up. Then `fib(3) = 1 + 1 = 2`, `fib(4) = 2 + 1 = 3`, `fib(5) = 3 + 2 = 5`.
4. **Recompute `fib(4)` from scratch.** Back at the root, `fib(6)` still needs its second child — and the clerk has no notebook, so the entire `fib(4)` subtree (nine calls) is rebuilt node by node. The status line calls it out: this argument has been seen before, and naive recursion does not care.
5. **Finish.** `fib(6) = 5 + 3 = 8`, after **25 calls** in total.

Switch the mode selector to **Memoization** and the same `fib(6)` resolves in **11 calls**: the second requests for `fib(2)`, `fib(3)`, and `fib(4)` arrive as cache-hit stubs that read straight out of the memo panel instead of growing subtrees. Switch to **Bottom-up** and there is no tree at all — the table fills `0, 1, 1, 2, 3, 5, 8`, three beats per cell: focus the empty slot, read the two cells before it, write the sum.

On screen, the tree reveals one node per call rather than appearing all at once; the two children light up as summands on each combine beat, and a value chip turns the node green when it returns. In memoized mode the left-hand memo panel is the notebook itself — a row fills on every `store`, and flashes on every hit. The running call counter in the header is the whole argument in one number: 25 versus 11.

## Time and Space Complexity

| Approach | Time | Space | What you see |
|---|---|---|---|
| Naive recursion | O(φⁿ) ≈ O(2ⁿ) | O(n) stack | `fib(6)` costs 25 calls; `fib(7)` costs 41 |
| Top-down memoization | O(n) | O(n) memo + O(n) stack | each subproblem solved once, then looked up |
| Bottom-up table | O(n) | O(n) table | one write per cell; O(1) if you keep only the last two values |

The exponential base is the golden ratio φ ≈ 1.618 — the call count of naive `fib(n)` grows like the Fibonacci numbers themselves, which is a pleasingly self-referential way to be doomed. The leap to O(n) time is the entire point of dynamic programming: it is the difference between `fib(50)` finishing instantly and not finishing at all.

## Edge Cases

- **`n = 0` and `n = 1`** are base cases — they return immediately with no recursion. The lesson's slider therefore starts at `n = 2`, the smallest input with a real recurrence, and caps at `n = 7`, where the naive tree already holds 41 nodes.
- **Base cases are never cache hits.** The displayed code checks `n < 2` before consulting the memo, so `fib(0)` and `fib(1)` never enter the notebook — there is nothing worth remembering about returning your own argument.
- **Python's `memo={}` default argument** persists across calls. Convenient here; a classic footgun anywhere the cache should not be shared.
- **Large `n`** overflows fixed-width integers in many languages long before O(n) becomes slow.

## Common Mistakes

- **Shipping the naive version.** It is correct, it passes small tests, and it times out the moment `n` grows — exponential cost hides well at `n = 10`.
- **Checking the cache before the base case.** Harmless-looking, but it pollutes the memo with entries the recurrence never needed and quietly changes which line your code exits through.
- **Off-by-one in the table.** `dp` needs length `n + 1`, and both `dp[0]` and `dp[1]` must be written before the loop, or the first iteration reads an empty cell.
- **Believing memoization changes the answer.** All three approaches return the same `fib(n)`. The notebook changes how much work the clerk does — never what the subtotal is.