Memoisation in Python: stop solving the same problem twice

The direct recursive Fibonacci function below recalculates smaller Fibonacci values along multiple branches. MIT’s algorithms course uses Fibonacci to introduce memoisation and the reuse of solutions to subproblems.^[2]

Remembering completed work

Memoisation stores a function result under the arguments that produced it. When those arguments recur, the cached result can be returned instead of executing the function body again. Python documents functools.cache as an unbounded memoising wrapper and describes it as a lightweight wrapper around a dictionary lookup.^[1]

Because a dictionary stores the results, the positional and keyword arguments must be hashable. An unbounded cache can retain entries until the cache is cleared or the wrapped function ceases to exist.^[1]

A baseline and a memoised version

The complete program calculates the same Fibonacci value with direct recursion and functools.cache. It counts function-body executions, cache hits and retained entries, then performs a documented timing comparison.

from __future__ import annotations
from functools import cache
from statistics import median
from timeit import repeat
import platform
import sys
N = 32
def fib_plain(n: int) -> tuple[int, int]:
    """Return Fibonacci(n) and the number of function bodies executed."""
    calls = 0
    def visit(k: int) -> int:
        nonlocal calls
        calls += 1
        if k < 2:
            return k
        return visit(k - 1) + visit(k - 2)
    return visit(n), calls
def fib_memoised(n: int) -> tuple[int, int, int, int]:
    """Return Fibonacci(n), executions, cache hits, and cache entries."""
    executions = 0
    @cache
    def visit(k: int) -> int:
        nonlocal executions
        executions += 1
        if k < 2:
            return k
        return visit(k - 1) + visit(k - 2)
    value = visit(n)
    info = visit.cache_info()
    return value, executions, info.hits, info.currsize
plain_value, plain_calls = fib_plain(N)
memo_value, memo_executions, memo_hits, memo_entries = fib_memoised(N)
assert plain_value == memo_value == 2_178_309
# Each timing includes one complete cold-cache computation.
plain_samples = repeat(lambda: fib_plain(N), number=1, repeat=7)
memo_batches = repeat(
    lambda: [fib_memoised(N) for _ in range(1_000)],
    number=1,
    repeat=7,
)
memo_samples = [sample / 1_000 for sample in memo_batches]
plain_median = median(plain_samples)
memo_median = median(memo_samples)
ratio = plain_median / memo_median
print(f"Python: {sys.version.split()[0]}")
print(f"Platform: {platform.platform()}")
print(f"Input: n={N}")
print(f"Result: {plain_value}")
print(f"Plain recursive executions: {plain_calls:,}")
print(f"Memoised function-body executions: {memo_executions}")
print(f"Memoised cache hits: {memo_hits}")
print(f"Memoised cache entries: {memo_entries}")
print(f"Plain median (7 single runs): {plain_median:.6f} s")
print(
    "Memoised cold-cache median (7 batches of 1,000): "
    f"{memo_median * 1e6:.3f} us"
)
print(f"Observed speed ratio: {ratio:,.1f}x")

Recorded local execution

The artefact was executed on 13 August 2026. Its deterministic results match the previously published benchmark: F(32) is 2,178,309; direct recursion executes 7,049,155 function bodies; the memoised version executes 33 function bodies, records 30 hits and retains 33 entries. The exact timing output from this execution follows.

Python: 3.13.5
Platform: Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41
Input: n=32
Result: 2178309
Plain recursive executions: 7,049,155
Memoised function-body executions: 33
Memoised cache hits: 30
Memoised cache entries: 33
Plain median (7 single runs): 1.804579 s
Memoised cold-cache median (7 batches of 1,000): 33.918 us
Observed speed ratio: 53,204.5x

For this recurrence, the uncached call tree branches into repeated subproblems, while memoisation evaluates the 33 distinct inputs F(0) through F(32) once each. MIT presents this change as reusing solutions to subproblems in a polynomial-time dynamic-programming method.^[2] The local counters demonstrate the effect for this implementation and input.

The measured speed ratio is not a general performance guarantee. A cache hit still uses the memoising wrapper and dictionary lookup described by Python, and the relative cost depends on the function, arguments, interpreter and workload.^[1]

Conditional selection criteria

Memoisation can reduce work when repeated calls use the same hashable arguments, the result remains valid for those arguments, and recomputation costs more than lookup and storage.^[1][2] The memory cost should be assessed against the number and lifetime of distinct keys.

If inputs rarely repeat, results depend on changing external state, or the key space grows without an acceptable bound, an unbounded cache does not meet those constraints. lru_cache(maxsize=...) supplies a bounded alternative when eviction is acceptable.^[1]

Memoisation does not remove recursive call depth. Python limits recursion to prevent an overflowing C stack, and excessive depth raises RecursionError; the platform-dependent limit should be changed only with care.^[3] For a dependency chain that may approach that limit, a bottom-up loop or explicit stack avoids reliance on recursive depth. For Fibonacci specifically, an iterative loop also computes successive values without retaining a cache of all inputs.

Sources

1. Python documentation: functools.cache and functools.lru_cache
2. MIT OpenCourseWare: Lecture 19 typed notes
3. Python documentation: recursion limit