Memoization Explained: Cache Recursive Calls in Python

Memoization is the cheapest big speedup in programming: one dictionary and two lines turn an exponential recursion into a linear one. It is also easy to get subtly wrong, by caching on the wrong key, by letting a cache outlive the problem it belongs to, or by memoizing something that was never safe to remember. This article is about the mechanism itself; how it relates to bottom-up tables is covered in memoization vs tabulation.

The problem it solves

Some recursions ask the same question many times. Naive Fibonacci computes fib(n - 1) and fib(n - 2), and fib(n - 1) computes fib(n - 2) all over again. The repeats compound: every distinct argument is recomputed once for every path that reaches it, and the number of calls grows exponentially.

That pattern, a small set of distinct subproblems reached by a huge number of paths, is what dynamic programming calls overlapping subproblems. Where there is no overlap, as in merge sort, where every call works on a different slice, memoization stores answers nobody asks for twice.

The intuition

Before computing, look the arguments up in a table. If they are there, return the stored answer. If not, compute, store, then return. Each distinct input is computed once; every later request is a lookup.

Three conditions make it correct:

• The result depends only on the arguments. A function that reads the clock, a random generator, a file or a global that changes will return stale answers from its cache.
• The key captures everything the result depends on. If a parameter changes the answer, it must be part of the key, or two different questions share one cached answer.
• The cache lives exactly as long as the problem. A cache shared between unrelated calls is only safe if the key is complete.

Python ships this as functools.lru_cache, and functools.cache (from 3.9) is the unbounded version. Both key on every argument, so arguments must be hashable: tuples rather than lists.

Watch it run

The animation reruns the same fib(5) call tree, with one line added: before recursing, look in a memo dictionary. f4 has not been solved yet, so it recurses, but only this once; so do f3 and f2. Then f1 is a base case: it answers directly and is never stored, because only its caller's sum goes into the memo; f0 and the next f1 are base cases too. When f4 asks for f2, it is already in the memo, so the stored answer comes back and that subtree is never opened. The same happens when f5 asks for f3. Everything greyed out at the end is work the naive version did anyway: two cache hits pruned six calls. The final count is 9 calls instead of 15, and for fib(35) it is 69 instead of nearly 30 million. Exponential to linear, paid for with one dictionary.

The code

A counting wrapper makes the difference measurable. Because the recursive calls go through the module-level name, the wrapper sees every one:

def counted(f):
    """Wrap a function so every call, including recursive ones, is counted."""
    def wrapper(*args):
        wrapper.calls += 1
        return f(*args)
    wrapper.calls = 0
    return wrapper

@counted
def fib_naive(n):
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)

memo = {}
@counted
def fib_memo(n):
    if n < 2:
        return n
    if n not in memo:                       # the one line that changes everything
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

print(fib_naive(25), fib_naive.calls)       # 75025 242785
print(fib_memo(25), fib_memo.calls)         # 75025 49
print(fib_memo(30), fib_memo.calls)         # 832040 60

Naive fib(n) makes 2·fib(n + 1) - 1 calls, here 242,785; the memoized one makes 2n - 1, here 49. The memo also persists: fib_memo(30) afterwards costs only 11 more calls, because 2 to 25 are already stored.

Persistence is also the classic bug. A mutable default argument is created once and shared by every call, so a memo keyed on n alone quietly answers a different question:

def ways(n, steps, memo={}):                # the shared default dict outlives the call
    if n < 0:
        return 0
    if n == 0:
        return 1
    if n not in memo:                       # keyed on n alone, but steps matters too
        memo[n] = sum(ways(n - s, steps, memo) for s in steps)
    return memo[n]

print(ways(10, (1, 2)), ways(10, (1, 3)))   # 89 89

from functools import lru_cache

@lru_cache(maxsize=None)
def ways_ok(n, steps):                      # the key is every argument: (n, steps)
    if n < 0:
        return 0
    if n == 0:
        return 1
    return sum(ways_ok(n - s, steps) for s in steps)

print(ways_ok(10, (1, 2)), ways_ok(10, (1, 3)))   # 89 28
print(ways_ok.cache_info())                 # CacheInfo(hits=17, misses=25, maxsize=None, currsize=25)
try:
    ways_ok(10, [1, 2])
except TypeError as e:
    print(type(e).__name__, e)              # TypeError unhashable type: 'list'

The second call to ways returned the first call's answer, 89, instead of 28. The lru_cache version keys on (n, steps), so the two questions stay apart, and it rejects a list outright rather than guessing. Finally, ways_ok is checked on 300 seeded random cases against a brute force that lists every sequence of steps and counts those that sum to n:

import random
from itertools import product

def brute(n, steps):
    """Count every sequence of steps that sums to exactly n, by listing them all."""
    total = 0
    for length in range(n + 1):
        for seq in product(steps, repeat=length):
            total += sum(seq) == n
    return total

rng = random.Random(34)
ok = True
for _ in range(300):
    n = rng.randint(0, 10)
    steps = tuple(sorted(rng.sample(range(1, 6), rng.randint(1, 3))))
    ok &= ways_ok(n, steps) == brute(n, steps)
print(ok, ways_ok.cache_info().currsize)    # True 330

The complexity

• Time: distinct subproblems times the work per subproblem, not counting recursive calls answered from the cache. Fibonacci: n subproblems, constant work each, so O(n).
• Space: one cache entry per distinct subproblem, plus the recursion depth on the call stack.
• Lookup: a hash of the arguments per call, O(1) on average for small keys; hashing large tuples is not free.

Where it goes wrong

• Incomplete keys. Any parameter that changes the result must be in the key.
• Mutable default memo. It survives between calls; pass None and create the dict inside, or use lru_cache.
• Impure functions. Caching a function with side effects or hidden inputs returns answers that are no longer true.
• Deep recursion. Memoization fixes the call count, not the depth: a cold fib_memo(5000) still recurses about 5,000 levels deep, past CPython's default limit of 1,000 frames as of October 2026. Go bottom-up, as the Python cheat sheet notes, or see tail recursion.
• Unbounded caches in long-running processes. maxsize=None grows forever; bound it or clear it.

When it shows up in interviews

Almost every dynamic programming question starts here: write the recursion, notice repeated subproblems, add a memo, then state the new complexity. Interviewers check that you can count distinct states, name what goes in the key, and explain when you would switch to a bottom-up table.

How to say it in an interview

"The recursion recomputes the same subproblems, so I memoize: before computing, I look the arguments up in a dictionary, and after computing I store the result. Each distinct state is computed once, so the time is the number of states times the work per state, and the space is one entry per state plus the recursion depth. It is only valid if the function is pure and the key includes every input that affects the answer. In Python I would use functools.cache, and if the depth could exceed the recursion limit I would convert it to a bottom-up table."