Fibonacci Memoization —
From O(2ⁿ) to O(n) with one dictionary.
The Recursion section's Fibonacci lesson showed fib(3) getting recomputed from scratch inside fib(5). Memoization fixes exactly that: cache each result the first time it's computed, and every later request for the same value returns instantly instead of recomputing. Watch the cache hit fire on LearnBug and see the exponential tree collapse into a straight line.
What is Memoization?
Store each computed result in a dictionary keyed by its input. Before computing fib(n), check if it's already in the cache — if so, return it immediately. If not, compute it (recursively), then save the result before returning. This is "top-down" dynamic programming: still recursive, just remembering what it's already solved.
Why visualization helps
A cache hit is invisible in the output — the function just returns a value, same as any other call. LearnBug highlights the specific moment a call checks the cache and finds something already there, so you can see the exact branch of the naive recursion tree that gets skipped entirely, not just told it would have been skipped.
The exact same function, with one addition
Naive — recomputes everything, every time
No memory between calls. fib(3) is recomputed as many times as it appears anywhere in the call tree — exponentially many times for larger n.
Memoized — computes each value exactly once
One dictionary, checked before computing and updated after. Every distinct fib(k) for k from 0 to n is computed exactly one time, ever.
Same recursive structure, same answer
Memoization doesn't change the algorithm's logic at all — it's the identical recursive definition, with a cache check bolted on. The output is byte-for-byte identical.
fib(5) memoized — watch the second fib(3) short-circuit
fib(5) → fib(4)'s branch computes fib(3), fib(2), fib(1), fib(0) — caching each one
Same dive as the naive version, but every result gets saved as it's computed: memo[1]=1, memo[0]=0, memo[2]=1, memo[3]=2, memo[4]=3.
fib(4) returns 3 (cached). Now fib(5) needs its own fib(3) — checks the cache FIRST
This is the exact moment that was wasteful in the naive version. Here, before recursing at all, the function checks if n in memo — and 3 is already there.
fib(5) = fib(4) + fib(3) = 3 + 2 = 5 — computed with one cache hit instead of a full recomputation
The entire subtree that fib(3) would have spawned (calls to fib(2), fib(1), fib(0) all over again) simply never happens. The dictionary lookup replaced potentially dozens of calls for larger n.
The savings grow explosively with n — fib(30) naive makes ~2.7M calls, memoized makes 31
At n=5 the difference is modest. At n=30, naive recursion becomes noticeably slow while memoized recursion is instant — because the naive tree's size grows exponentially, but the memoized version only ever computes each of the n+1 distinct values once.
Return: fib(5) = 5 ✓ same answer, exponentially less work as n grows
Naive vs memoized, side by side
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2) # no memory between callsdef fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n] # CACHE HIT — skip recomputing this subtree entirely
if n <= 1:
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
print(fib_memo(5)) # 5Complexity Notes
Frequently asked questions
Why check "if n in memo" before checking the base case?
Order matters for efficiency but not correctness here — checking the cache first means even base-case values (0 and 1) benefit from caching once they've been computed once, avoiding the tiny but real overhead of re-evaluating n <= 1 unnecessarily on repeat calls.
Why use memo=None as the default instead of memo={}?
Python's default arguments are evaluated once, at function definition time, not on every call — a mutable default like {} would be silently shared and accumulate stale entries across separate, unrelated calls to fib_memo. Using None and creating a fresh dictionary inside the function avoids that classic Python pitfall entirely.
Is memoization the same thing as dynamic programming?
Memoization is one specific style of DP — "top-down," meaning you still write the natural recursive definition and add caching. The other main style is "bottom-up" (tabulation), where you build up an array iteratively from the base cases instead of recursing — see Climbing Stairs for a bottom-up example of the same idea.
Does memoization work for every recursive function?
It helps specifically when there are overlapping subproblems — the same input recurring across different branches of the recursion, as with Fibonacci. For recursive functions where every call has genuinely unique arguments (like merge sort's array-splitting calls, which always operate on different sub-arrays), memoization has nothing to cache and provides no benefit.
Watch the cache hit skip an entire subtree
Paste memoized Fibonacci into LearnBug and see exactly which calls get short-circuited.