Memoization (top-down DP) — recursive + memo dict: Visual walkthrough

We build everything around one small example: computing $F (5)$ , the 5th Fibonacci number. Small enough to draw the entire call tree, big enough to show the waste.

Step 1 — What is a "recurrence"? (the rule that makes small from big)

WHAT. A recurrence is a rule that says: "the answer for a big input is made out of the answers for smaller inputs." For Fibonacci the rule is

$answer we want F (n) = answer for input one smaller F (n - 1) + answer for input two smaller F (n - 2)$

with two starting facts we are simply told (no rule needed for them):

$base fact F (0) = 0, base fact F (1) = 1$

WHY. Every symbol here is earned: $F$ is just a name for "the function that eats a number $n$ and hands back the $n$ -th Fibonacci value." The little $(n - 1)$ and $(n - 2)$ are smaller inputs, so the rule always points downward toward the two base facts. Without those two base facts the rule would keep asking for smaller and smaller inputs forever — like a staircase with no bottom step.

PICTURE. Below, the big node is what we want; the two arrows point to the two smaller things it needs. That single fork, repeated, is the whole algorithm.

Figure — Memoization (top-down DP) — recursive + memo dict

Step 2 — Unfold the rule fully: the naive call tree for $F (5)$

WHAT. Apply the rule from Step 1 over and over. $F (5)$ needs $F (4)$ and $F (3)$ . Each of those needs its own two children, and so on, until every branch ends at a base fact $F (0)$ or $F (1)$ .

WHY. We unfold before optimising because you cannot see waste you have not drawn. This tree is exactly what a plain recursive function does — each node is one function call, each leaf is a base case that returns immediately.

PICTURE. The complete tree. Count the nodes: there are 15 of them. Notice how fat the tree is at the bottom — that fatness is the enemy.

Step 3 — Find the repeats: the same subproblem, over and over

WHAT. Walk the tree from Step 2 and colour every node by its input value. Count how many times each distinct input appears:

input $n$	times computed in naive tree
$F (4)$	1
$F (3)$	2
$F (2)$	3
$F (1)$	5
$F (0)$	3

WHY. This table is the entire justification for caching. $F (2)$ is asked for 3 separate times, and its answer is always $1$ . Recomputing it is pure waste — like re-adding $1 + 1$ from scratch three times. The deeper you go, the worse it gets: for $F (n)$ the number of nodes grows like $ϕ^{n}$ where

$ϕ = \frac{1 + 5}{2} \approx 1.618 (the golden ratio) .$

PICTURE. Same tree, now colour-coded. Every node sharing a colour is the identical subproblem. Your eye immediately sees the duplication.

Recall

Why is recomputing $F (3)$ twice pointless? ::: Its answer ( $2$ ) never changes — it depends only on its input, so the second computation must give the same result as the first.

Step 4 — Introduce the memo: a sticky-note notebook

WHAT. Create one dictionary — call it $memo$ — that maps an input to its already-computed answer:

$memo [n] = the value of F (n), once we know it .$

We add one new rule at the top of every call: before doing any work, ask "is $n$ already a key in $memo$ ?" If yes, hand back $memo [n]$ instantly and stop.

WHY. The dictionary (see Hash Maps / Dictionaries) gives us an $O (1)$ lookup — reading an already-known answer costs a flat, tiny amount of time no matter how big $n$ is. That is why a hash map and not, say, a list scan: we want "have I seen this exact state?" answered in one step. This turns the repeated-work problem into a look-it-up problem.

PICTURE. The notebook fills up left-to-right as computation proceeds. Grey cells are still empty (unknown); filled cells are answers we will never recompute.

Step 5 — Prune the tree: what the memo actually cuts

WHAT. Re-run $F (5)$ , but now the first time we finish a subproblem we store it, and every later request for it is answered from the notebook — its whole subtree never gets drawn.

WHY. The order of a recursion is depth-first (leftmost branch all the way down first). So $F (3)$ , $F (2)$ , $F (1)$ , $F (0)$ all get computed and stored while we work down the left side of the tree. When the right side later asks for $F (3)$ , it hits the cache immediately — that entire right subtree, which had 5 nodes, collapses to a single lookup.

PICTURE. The pruned tree: solid nodes are computed once; the greyed-out, crossed subtrees are the ones the cache skipped. Compare the surviving nodes to the fat tree of Step 2.

Step 6 — Count what survives: the exponential-to-linear collapse

WHAT. After pruning, how many nodes actually do real work? Exactly one per distinct input: $F (0), F (1), F (2), F (3), F (4), F (5)$ — that is $n + 1 = 6$ nodes. Every other node in the original tree became a cache hit.

WHY. This is the punchline of the whole paradigm, and it's just arithmetic:

$total time = n + 1 (number of distinct states) \times O (1) (work per state) = O (n) .$

Compare the two growth curves. The naive count follows $ϕ^{n}$ (doubling-ish every step); the memoized count follows the straight line $n + 1$ . For $n = 5$ that's $15$ vs $6$ ; for $n = 40$ it's about 330 million vs 41. (See Time Complexity Analysis — we count distinct states, never raw calls.)

PICTURE. The two curves on one chalkboard: the runaway exponential vs the tame straight line.

Step 7 — The degenerate cases (never let the reader hit an untested input)

WHAT & WHY & PICTURE, one per case:

Case $n = 0$ and $n = 1$ (pure base facts). The rule from Step 1 is never applied; the base line returns immediately. The tree is a single node — no fork at all. If you forgot these, the recursion would ask for $F (- 1)$ , $F (- 2)$ , ... forever.

Case: cache check missing (the "no notebook" bug). If you delete the $C$ heck line, you have Step 2's fat tree back — correct answer, exponential time. The code looks fine and gives right results on tiny inputs, which is exactly what makes this bug sneaky.

Case: store forgotten (the "empty notebook" bug). If you recurse but never write $memo [n] = \dots$ , the check always misses because nothing is ever stored. Same fat tree, same waste. Store before you return.

The one-picture summary

Left: the fat naive tree (15 nodes, waste in colour). Right: the pruned memoized run (6 real nodes + arrows to the notebook). Bottom: the two growth curves. One glance carries the whole derivation.

Recall Feynman retelling — the whole walkthrough in plain words

We wanted the 5th Fibonacci number. The rule "big equals two smaller ones" (Step 1) unfolds into a bushy tree of little calls (Step 2). When we coloured that tree we caught it red-handed: the same tiny sums appear again and again — $F (2)$ three times, $F (1)$ five times (Step 3). So we grabbed a notebook, the memo dict, and made one promise: every time we finish a small sum we jot the answer down, and before doing any sum we first peek at the notebook (Step 4). Now when the right half of the tree asks for something the left half already solved, we just read the note — the whole branch vanishes (Step 5). Counting only the sums we truly did, there's just one per distinct number: six of them instead of fifteen, and for big inputs it's millions-vs-dozens (Step 6). Finally we made sure nothing bites us: the two base facts stop the falling forever, and the two classic bugs — forgetting to peek, or forgetting to jot down — both quietly hand you the slow fat tree back (Step 7). That's memoization: recursion that remembers.

Connections

Recursion — the tree in every step is recursion; memoization only adds the notebook
Dynamic Programming — this collapse is the heart of the paradigm
Tabulation (Bottom-up DP) — fills the same notebook, but bottom row first, no tree
Time Complexity Analysis — Step 6 is "distinct states × work per state"
Divide and Conquer — recursion without the coloured repeats of Step 3
Hash Maps / Dictionaries — the $O (1)$ notebook of Step 4
lru_cache decorator — Python's built-in memo, the fix in Step 7