From Recursion to Memoization to a Table
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Many problems are easy to say as a recursion and slow to run. Saving each answer once turns an exponential program into a linear one. This lesson shows the three steps: recursion, memoization, table.
Big problems made of smaller copies
Dynamic programming is solving a problem by splitting it into smaller subproblems, solving each one once and reusing the answers. It works when subproblems repeat and the answer is built from smaller answers.
Each Fibonacci number is the sum of the two before it. So the answer for n is built from the answers for n - 1 and n - 2, and plain recursion says exactly that.
def fib(n): if n < 2: return n return fib(n - 1) + fib(n - 2)
print(fib(10))It is correct, but slow: the same calls run again and again, as the picture shows.
Example 1 · Count the calls
calls = 0
def fib(n): global calls calls += 1 if n < 2: return n return fib(n - 1) + fib(n - 2)
fib(20)print("plain calls:", calls)
calls = 0memo = {}
def fib_memo(n): global calls calls += 1 if n < 2: return n if n not in memo: memo[n] = fib_memo(n - 1) + fib_memo(n - 2) return memo[n]
fib_memo(20)print("memo calls:", calls)plain calls: 21891 memo calls: 39
What this code does
- Plain recursion makes thousands of calls for n = 20. With a dictionary as memory it makes about 2n.
- The only change is
if n not in memo: compute once, then reuse.
The base cases n < 2 stop the recursion. The call tree doubles at every level, so fib(40) takes seconds. It is O(2^n) time because it rebuilds fib(3), fib(2) and the rest many times.
Memoization: remember each answer
Memoization is saving the result of a function for each input, so a repeated call returns the saved answer instead of computing it again.
Save each answer the first time you compute it. A later call with the same input reads the saved answer. functools.lru_cache does this with one line above the function.
from functools import lru_cache
@lru_cache(maxsize=None)def fib(n): if n < 2: return n return fib(n - 1) + fib(n - 2)
print(fib(80))Example 2 · Memoize with a dictionary
def ways(n, memo=None): if memo is None: memo = {} if n < 2: return 1 if n not in memo: memo[n] = ways(n - 1, memo) + ways(n - 2, memo) return memo[n]
print([ways(n) for n in range(8)])[1, 1, 2, 3, 5, 8, 13, 21]
What this code does
- The memo dictionary is passed down so every call shares it. Creating it with
memo=Noneavoids the shared default-argument trap. - Writing
memo={}in the signature would keep one dictionary for the whole program.
Example 3 · Look inside the cache
from functools import lru_cache
@lru_cache(maxsize=None)def fib(n): return n if n < 2 else fib(n - 1) + fib(n - 2)
fib(10)print(fib.cache_info())fib.cache_clear()print(fib.cache_info().currsize)CacheInfo(hits=8, misses=11, maxsize=None, currsize=11) 0
What this code does
cache_info()shows hits, misses and how many answers are stored. Eleven answers for 0 to 10 means each was computed once.cache_clear()empties the cache, which matters when the function depends on data that changes.
Each n is computed once, so time is O(n) and the cache holds n answers, which is O(n) space. Python integers never overflow, so fib(80) is exact.
A table, filled from the bottom
Memoization starts at the big problem and goes down. A table goes the other way: fill the answers for 0, 1, 2 and so on up to n, so every answer you need already exists.
n = 10dp = [0] * (n + 1)dp[1] = 1for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2]print(dp)Example 4 · Three previous cells
n = 12dp = [0, 0, 1] + [0] * (n - 2)for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]print(dp)[0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274]
What this code does
- A transition can read any smaller cells. Here each cell is the sum of the three before it.
- The base cells are written by hand. The loop starts where the rule begins to apply.
dp[i] is the answer for i. The loop goes upward, so dp[i - 1] and dp[i - 2] are always ready. Time is O(n) and space is O(n). With n = 0 the line dp[1] = 1 would fail, so a real program guards small n.
State, transition and base case
A state is the small set of values that names one subproblem, such as n. A transition is the rule that builds the answer of a state from the answers of smaller states.
To design any table, answer four questions. What does one cell mean? What are the first cells you know without thinking? How does a cell use smaller cells? Which cell holds the final answer?
def fib(n): a, b = 0, 1 for _ in range(n): a, b = b, a + b return a
print(fib(10))Example 5 · Tiling a strip
# ways to cover a 2 x n strip with 2 x 1 tiles, standing or lying in pairsn = 8dp = [1, 1] + [0] * (n - 1)for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2]print(dp[1:])[1, 2, 3, 5, 8, 13, 21, 34]
What this code does
- The last column is either one standing tile, leaving a strip of n - 1, or two lying tiles, leaving n - 2.
- That sentence is the transition. Finding it is the real work of dynamic programming.
Example 6 · Deep recursion against a table
from functools import lru_cache
@lru_cache(maxsize=None)def fib(n): return n if n < 2 else fib(n - 1) + fib(n - 2)
try: fib(5000)except RecursionError: print("RecursionError")
a, b = 0, 1for _ in range(5000): a, b = b, a + bprint(len(str(a)))RecursionError 1045
What this code does
- Python limits recursion to about 1000 levels, so memoized recursion fails for large n. The loop has no such limit.
- The answer has 1045 digits and is still exact, because Python integers grow as needed.
Only the last two answers are ever read, so two variables replace the whole table and space drops to O(1). The tuple assignment updates both values at once.
Next step
Check your understanding
11 quick questions