Memoization with functools.lru_cache
22 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A recursive function can ask the same question again and again. Memoization saves each answer the first time so repeats cost one lookup. This lesson shows the problem on a call tree, the dictionary fix, and Python's one-line version, functools.lru_cache.
The same question asked again
Overlapping subproblems means a recursion asks the same smaller question many times. The call tree shows it as repeated nodes, and each repeat wastes time.
Fibonacci numbers add the previous two. A recursive version asks for fib(2) many times, because the smaller calls overlap.
calls = 0
def fib(n): global calls calls += 1 if n < 2: return n return fib(n - 1) + fib(n - 2)
print(fib(20))print(calls)Example 1 · How the work grows
calls = 0
def fib(n): global calls calls += 1 return n if n < 2 else fib(n - 1) + fib(n - 2)
for n in (10, 20, 25): calls = 0 fib(n) print(n, calls)10 177 20 21891 25 242785
What this code does
- The calls grow about 1.6 times for each step of n.
- Going from 20 to 25 multiplies the work by roughly 11.
Finding fib(20) took 21,891 calls, and each extra step roughly multiplies the work by 1.6. The cost is exponential, about O(2 to the n).
Remember answers in a dictionary
Memoization is saving the result of a function for each set of arguments, so a repeated call returns the saved result instead of computing it again.
If every answer is stored the first time, a repeat question costs one lookup. The dictionary is checked before any work is done.
memo = {}
def fib(n): if n < 2: return n if n not in memo: memo[n] = fib(n - 1) + fib(n - 2) return memo[n]
print(fib(80))Example 2 · Dictionary memo with a counter
memo = {}calls = 0
def fib(n): global calls calls += 1 if n < 2: return n if n not in memo: memo[n] = fib(n - 1) + fib(n - 2) return memo[n]
print(fib(25))print(calls)75025 49
What this code does
- The answer is the same, but the calls drop from 242,785 to 49.
- Each fib(k) does its real work once. Repeat calls return at the dictionary check.
Each value from 2 to 80 is computed once. That is O(n) time and O(n) space, down from exponential time.
functools.lru_cache does it for you
functools.lru_cache is a decorator that caches a function's results by its arguments. The name means least recently used: with a size limit, the oldest unused results are dropped first.
Writing the dictionary every time is noise. The decorator lru_cache wraps a function and keeps its own table of results.
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))print(fib.cache_info())Example 3 · Grid paths: slow, then cached
from functools import lru_cache
slow_calls = 0
def slow(rows, cols): global slow_calls slow_calls += 1 if rows == 0 or cols == 0: return 1 return slow(rows - 1, cols) + slow(rows, cols - 1)
@lru_cache(maxsize=None)def fast(rows, cols): if rows == 0 or cols == 0: return 1 return fast(rows - 1, cols) + fast(rows, cols - 1)
print(slow(10, 10), slow_calls)print(fast(10, 10), fast.cache_info().misses)184756 369511 184756 120
What this code does
- The task is to count the routes from one corner of a grid to the other, moving right or down.
- The slow version makes 369,511 calls. The cached version computes only 120 different cells.
Example 4 · Hits, misses and clearing
from functools import lru_cache
@lru_cache(maxsize=None)def square(n): return n * n
for n in (3, 4, 3, 3): square(n)print(square.cache_info())square.cache_clear()print(square.cache_info())CacheInfo(hits=2, misses=2, maxsize=None, currsize=2) CacheInfo(hits=0, misses=0, maxsize=None, currsize=0)
What this code does
- Two new numbers are misses, and the two repeated 3s are hits.
cache_clear()empties the table, for example between tests.
maxsize=None keeps every result. cache_info() counts hits (answers reused) and misses (answers computed).
Rules for caching
Pure function is a function whose result depends only on its arguments and which changes nothing outside itself. Only pure functions are safe to cache, because the same call must always give the same answer.
The cache key is the argument values, so they must be hashable. A list cannot be a key, but a tuple can.
from functools import lru_cache
@lru_cache(maxsize=None)def total(items): return sum(items)
try: total([1, 2, 3])except TypeError: print("a list cannot be a cache key")print(total((1, 2, 3)))Example 5 · Cache key must be hashable
from functools import lru_cache
@lru_cache(maxsize=None)def cost(items): return sum(items)
order = [5, 10, 15]try: cost(order)except TypeError as error: print(error)print(cost(tuple(order)))unhashable type: 'list' 30
What this code does
- A list can change, so Python refuses to use it as a key.
- Convert it to a tuple before the call.
Only cache pure functions. A cached function that reads the time, a file or a global returns stale answers.
Caching does not remove the depth
A cached recursion still makes nested calls, so the recursion limit still applies. For a deep chain, fill the answers from the bottom up instead.
Example 6 · A deep chain: bottom-up instead
from functools import lru_cache
@lru_cache(maxsize=None)def fib(n): return n if n < 2 else fib(n - 1) + fib(n - 2)
def fib_up(n): previous, current = 0, 1 for _ in range(n): previous, current = current, previous + current return previous
try: fib(2000)except RecursionError: print("cached recursion too deep")print(len(str(fib_up(2000))), "digits")cached recursion too deep 418 digits
What this code does
- Even with a cache, fib(2000) needs about 2000 nested calls.
- The loop keeps only the last two values: O(n) time and O(1) space.
Next step
Check your understanding
10 quick questions