Memoization caches the result of each unique recursive call so repeated subproblems aren't recomputed. It turns exponential naive recursion into polynomial dynamic programming with one decorator.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n) |
Θ(states) |
O(states) |
O(states) |
Wrap the recursive function in a cache keyed by its arguments. The first call with a given argument tuple does the real work and stores the result; every subsequent call returns the cached value in O(1). Total time = (work per state) × (number of unique states).
from functools import cache
# Naive Fibonacci is O(2^n).
def fib_naive(n):
if n < 2: return n
return fib_naive(n - 1) + fib_naive(n - 2)
# Memoized — O(n) time, O(n) space.
@cache
def fib(n):
if n < 2: return n
return fib(n - 1) + fib(n - 2)
print(fib(50)) # 12586269025 — instant
# 2-D memoization for unique-paths-in-grid:
@cache
def unique_paths(m, n):
if m == 1 or n == 1: return 1
return unique_paths(m - 1, n) + unique_paths(m, n - 1)
print(unique_paths(7, 3)) # 28
# functools.cache is unbounded; use lru_cache(maxsize=N) to cap it.
from functools import lru_cache
@lru_cache(maxsize=1024)
def expensive(x): ...Memoization pays off when a recursive function has two properties. First, overlapping subproblems: the same arguments are requested many times, as in the Fibonacci call tree above where fib(3) and fib(2) appear repeatedly. Second, purity: the result depends only on the arguments, so a cached value is always correct. Merge sort, by contrast, never repeats a subproblem, so caching it adds overhead with no benefit. The number of distinct states, not the size of the call tree, determines the memoized running time: time is states multiplied by the work per state, and space is the number of cached states plus the recursion depth.
A useful way to spot candidates is to write the plain recursive solution first and then ask what uniquely identifies a call. If the answer is a small tuple of integers, such as an index, a remaining capacity, or a pair of positions in two strings, the number of distinct states is the product of their ranges, and memoization will bound the running time by that product. Problems such as edit distance, longest common subsequence, knapsack, counting paths in a grid, and word break all follow this pattern. If the identifying information includes a whole set or a list that grows, the state space may still be exponential and memoization only helps partially.
With a cache, the first descent computes fib(5), fib(4), fib(3), and fib(2) once each, bottoming out at the base cases. On the way back up, the second recursive call at each level finds its answer already in the cache. Six distinct states (0 through 5) are evaluated once, so the work is linear instead of exponential.
The same idea generalizes beyond Fibonacci. Memoization converts the call tree into a directed acyclic graph of states, where each edge is a recursive call and each node is evaluated exactly once. Any order that evaluates a node after all of its dependencies gives the same answer, which is why the top-down version and the bottom-up table in the next section are interchangeable. Choosing between them is a matter of convenience, depth limits, and memory, not correctness.
from functools import cache
import sys
def min_coins(coins: tuple[int, ...], amount: int) -> int:
@cache
def best(rem: int) -> float:
if rem == 0:
return 0
if rem < 0:
return float("inf")
return 1 + min(best(rem - c) for c in coins)
ans = best(amount)
return -1 if ans == float("inf") else int(ans)
print(min_coins((1, 5, 10, 25), 63)) # 6 (25+25+10+1+1+1)
# Same recurrence, bottom-up: no recursion depth limit
def min_coins_dp(coins, amount):
dp = [0] + [float("inf")] * amount
for a in range(1, amount + 1):
dp[a] = 1 + min((dp[a - c] for c in coins if c <= a), default=float("inf"))
return -1 if dp[amount] == float("inf") else dp[amount]
sys.setrecursionlimit(10_000) # only if you must recurse deeplyHere the state is the remaining amount, so there are at most amount + 1 states, each doing len(coins) work: O(amount x coins) time and O(amount) space. The cache is defined inside the outer function so it is discarded between calls with different coin sets.
| Aspect | Top-down memoization | Bottom-up tabulation |
|---|---|---|
| Code shape | Natural recursive definition | Explicit loop order |
| States computed | Only those reachable | All states in the table |
| Recursion depth | Can hit Python's limit (about 1000) | None |
| Space optimization | Hard | Often reducible to O(1) rows |
| Overhead | Function calls and hashing | Array indexing |
In interviews and production code alike, a reasonable workflow is to write the recursive version with @cache to confirm the recurrence is correct, then convert it to a table if profiling or input size demands it. The recurrence is the hard part; the conversion is mechanical once the dependency order of the states is clear.
@cache keeps self alive in the cache; prefer a cache inside the method or on the instance.fn.cache_clear() when inputs change meaning.