Memoization
Lesson 5-2 ended with the diagnosis: naive fib is exponential because it re-solves the same subproblems. The cure is embarrassingly simple:
Keep a dictionary. Before computing, check it. After computing, store the answer in it.
That dictionary is called a memo (hence memoization), and it changes the math completely: each distinct argument is computed once, and every repeat is an O(1) dictionary hit. For fib that means O(n) total instead of O(2ⁿ).
The recipe for memoizing any recursive function:
if n in memo: return memo[n]at the top.- Compute as usual.
memo[n] = resultbefore returning.
Code exercise · python
Run this. Same fib, plus a memo dictionary. Compare with lesson 5-2: fib(20) drops from 21,891 calls to 39, and fib(50), which would take years naively, finishes instantly in 99 calls.
Quiz
Memoized fib makes about 2n calls instead of 2ⁿ. What exactly did the memo eliminate?
Code exercise · python
Your turn. The tribonacci sequence: trib(0)=0, trib(1)=1, trib(2)=1, and after that the sum of the previous THREE values. Write it with memoization, or trib(25) will make you wait.
@lru_cache: memoization as one line
Memoizing by hand teaches the mechanism, but in production Python you will usually reach for functools.lru_cache from the standard library. It is a decorator — a line starting with @ placed above a function that wraps the function with extra behavior. Here the behavior is exactly your memo: check a cache before computing, store the result after, keyed by the arguments. You also get a free cache_info() report.
Two cautions that both interviews and code review catch:
- Arguments must be hashable (numbers, strings, tuples — not lists), because they become dictionary keys under the hood.
- The cache lives as long as the function does.
maxsize=Nonemeans unbounded; long-running services usually set a bound so memory cannot grow forever — the "lru" (least recently used) policy then evicts the stalest entries first.
Code exercise · python
Run this. One decorator line memoizes fib. cache_info() reports 81 distinct computations (misses) and 78 cache hits — without the cache, fib(80) would take around 2⁸⁰ calls.
Problem
A memoized recursive function has n distinct subproblems, and each one does O(1) work besides its recursive calls. In Big-O, what is the total running time? Answer like O(n), O(n²), O(2^n).