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): ...