PYTHON / DATA STRUCTURES AND ALGORITHMS
Recursion, memoisation, and dynamic programming
Recognise overlapping subproblems in a recursion, cache them with a memo, and convert the result into a bottom-up dynamic programming loop.
What you will learn
- Spot overlapping subproblems by counting how many calls a recursion actually makes
- Add functools.lru_cache or a dict memo so cost = distinct states x work per state
- Rewrite a top-down memo as a bottom-up loop to escape Python's recursion limit
- Collapse a DP table to rolling variables when a state depends only on the last few
Understanding Recursion, memoisation, and dynamic programming
A recursive function describes a value in terms of smaller instances of itself, so every call is a frame pushed onto the call stack that waits for its children to return. The useful mental picture is not the function text but the recursion tree: fib_naive(5) calls fib_naive(4) and fib_naive(3), each of which expands again, until the leaves are base cases. Counting the nodes in that tree is how you get the real cost, and for the naive Fibonacci the node count is 2*F(n+1)-1, which grows exponentially even though only n+1 different questions are ever being asked.
The reason that tree is so wasteful is that the same node appears in it many times: fib_naive(20) is recomputed from scratch in thousands of different branches. Memoisation stores each answer in a dictionary keyed by the arguments, so a repeated question is answered by a lookup instead of a subtree. That turns the tree into a directed acyclic graph and makes the total cost the number of distinct states multiplied by the work done per state, which is why memoised Fibonacci runs in linear time with the identical recurrence.
Dynamic programming is the same recurrence evaluated in the opposite direction. Instead of asking for state n and letting recursion discover its dependencies, you order the states so that everything a state needs is already computed, then fill them with a loop. That buys three things: no call frames, so no RecursionError; no hash lookup or wrapper call per state; and the freedom to throw away table entries you will never read again, which is how the Fibonacci table shrinks to two variables. Top-down memoisation is usually easier to derive from the recurrence, so write it first and rewrite it bottom-up only when depth or speed demands it.
import functools
calls = 0
def fib_naive(n):
global calls
calls += 1
if n < 2:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
functools.lru_cache(maxsize=None)
def fib_memo(n):
if n < 2:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
def fib_table(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
value = fib_naive(25)
print("naive :", value, "-> calls:", calls)
print("memoised:", fib_memo(25), "->", fib_memo.cache_info())
print("bottom-up:", fib_table(25))
print("F(100) :", fib_table(100))Memoisation and dynamic programming are one idea - solve each distinct subproblem exactly once - differing only in whether you walk the recursion tree top-down with a cache or fill the states bottom-up in dependency order.
Worked examples
Explicit dict memo for coin change
Shows that the memo dictionary is literally the DP table, with one entry per distinct subproblem.
def min_coins(amount, coins):
memo = {}
def best(rem):
if rem == 0:
return 0
if rem < 0:
return float("inf")
if rem not in memo:
memo[rem] = 1 + min(best(rem - c) for c in coins)
return memo[rem]
return best(amount), len(memo)
for amount in (63, 11):
used, states = min_coins(amount, (1, 5, 21, 25))
print(f"{amount} -> {used} coins, {states} memo entries")Example explained
Line 1`if rem not in memo` is the entire memoisation pattern: look up, compute on miss, store before returning.
Line 2The memo ends up with one key per remaining amount from 1 to the target, so its size is exactly the state count you would allocate in a bottom-up table.
Line 3The recurrence `1 + min(best(rem - c) for c in coins)` finds 21+21+21 for 63, whereas greedy largest-coin-first would answer 7 with 25+25+5+5+1+1+1.
Line 4`memo` is created inside `min_coins`, so it is tied to one coin set; a module-level cache keyed only on `rem` would return wrong answers for a different set of coins.
lru_cache requires hashable arguments
Demonstrates that the cache key is built by hashing the argument tuple, so mutable arguments fail before the body runs.
from functools import lru_cache
lru_cache(maxsize=None)
def lcs(a, b):
if not a or not b:
return 0
if a[0] == b[0]:
return 1 + lcs(a[1:], b[1:])
return max(lcs(a[1:], b), lcs(a, b[1:]))
print("lcs:", lcs("dynamic", "programming"))
try:
lcs(list("abc"), list("abd"))
except TypeError as e:
print("TypeError:", e)Example explained
Line 1Each call peels one character off one string, so many different call paths arrive at the same pair of suffixes - that overlap is what the cache exploits.
Line 2Strings and tuples are hashable, so the wrapper can build a dict key from `(a, b)` and reuse the stored answer.
Line 3Passing lists raises TypeError inside the wrapper while it hashes the arguments, so the function body never executes; the fix is `tuple(...)` or passing integer indices instead of slices.
Line 4The answer 3 comes from the subsequence "ami"; `n` cannot join it because in "programming" the only `n` sits after the `a`.
Recursion depth is a hard ceiling
Shows why a correct linear-time recursion can still fail, and that the bottom-up version has no such limit.
import sys
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
def sum_to_loop(n):
total = 0
for i in range(1, n + 1):
total += i
return total
print("limit:", sys.getrecursionlimit())
print("sum_to(800):", sum_to(800))
try:
sum_to(50000)
except RecursionError:
print("sum_to(50000): RecursionError")
print("sum_to_loop(50000):", sum_to_loop(50000))Example explained
Line 1`sys.getrecursionlimit()` reports the default 1000, and `sum_to(n)` needs n+1 nested frames, so 800 fits and 50000 does not.
Line 2CPython does not optimise the tail call in `return n + sum_to(n - 1)`; the addition still has to happen after the child returns, so the frame must stay alive.
Line 3RecursionError is a normal exception you can catch, but catching it does not solve anything - the loop version computes the same value with one frame.
Line 4This is the practical reason to convert a deep top-down memo into a bottom-up table even when the memo is already fast enough.
Shrinking a DP table to rolling values
Shows how a one-dimensional table collapses when each state only reads a fixed window of earlier states.
def tribonacci_table(n):
table = [0] * (n + 1)
table[1] = table[2] = 1
for i in range(3, n + 1):
table[i] = table[i - 1] + table[i - 2] + table[i - 3]
return table[n], len(table)
def tribonacci_rolling(n):
a, b, c = 0, 1, 1
for _ in range(n - 2):
a, b, c = b, c, a + b + c
return c
print(tribonacci_table(20))
print(tribonacci_rolling(20))Example explained
Line 1The table version stores all 21 states even though state `i` only ever reads `i-1`, `i-2` and `i-3`.
Line 2`a, b, c = b, c, a + b + c` builds the right-hand tuple first, so all three old values are still available during the update.
Line 3Memory drops from O(n) to O(1) while the number of additions stays identical, which is the standard space optimisation for any DP with a bounded dependency window.
Line 4You lose the ability to reconstruct the full sequence afterwards, so keep the table when you need to trace the solution back.
Important notes
Memoisation only pays off when states repeat. Caching a recursion that never revisits a state - binary search, quicksort partitioning, plain tree traversal - just adds hashing cost and unbounded memory growth.
`functools.cache` is shorthand for `lru_cache(maxsize=None)` in Python 3.9+, and both key on the exact call form, so `f(3)` and `f(n=3)` occupy separate cache entries.
Common mistakes
Decorating a function whose arguments include a list, dict or set with lru_cache: the wrapper hashes the argument tuple to build a key, so you get `TypeError: unhashable type: 'list'` before the body runs. Convert to a tuple or pass indices.
Memoising a function that also reads mutable outer state, such as a global grid or a coin list not included in the arguments. Change that state and the cache silently returns answers for the old data - no error, just wrong results until you call `cache_clear()`.
Calling `sys.setrecursionlimit(10**6)` to make a deep recursion work. Python's limit only guards the C stack it cannot measure, so the process can segfault instead of raising a catchable RecursionError; rewrite bottom-up or use an explicit stack.
Try it yourself
Change, predict, then run
Write `grid_paths(rows, cols)` that counts routes from the top-left cell to the bottom-right cell moving only right or down: first as a recursion with an explicit dict memo, printing both `grid_paths(10, 10)` and the number of memo entries, then again as a single list you overwrite row by row and confirm the two agree.
Open the Python workspaceCheck your understanding
A recursive function takes three integer parameters, each in the range 0..99, does O(1) work per call, and makes up to four recursive calls. After adding a correct memo keyed on all three parameters, what is the worst-case running time?
- About 10^6 steps, because there are 100^3 distinct states and each is computed once
- About 4^300 steps, because the recursion still branches four ways at every level
- About 300 steps, since the memo reduces the work to the size of the parameter ranges
- Unchanged, because a memo saves recomputation of memory but not of time
Show answer
With a memo the cost is (number of distinct states) x (work per state), and the state space here is 100 x 100 x 100 = 10^6 with O(1) work each. The branching factor of four only decides how many cache probes happen per state, and every probe after the first miss returns immediately, which is exactly what collapses the exponential tree - so 4^300 describes the unmemoised version, not this one.