Memoisation

Add a memo dict to recursive Fibonacci, then use @lru_cache as the Pythonic shorthand, and watch call counts drop from exponential to linear.

Top-down DP is the simplest form of memoisation: write the recursion you already understand, then add one cache lookup and one cache store. Everything else stays the same.

Three implementations side by side

The code below defines three versions of Fibonacci. Each uses a call counter so you can compare exactly how many recursive calls each approach makes for the same input. Run it as-is, then try increasing N to 35 or 40.

Python — editable, runs in your browser

import functools

call_counts = {"naive": 0, "memo": 0, "cached": 0}

def fib_naive(n):
  call_counts["naive"] += 1
  if n <= 1:
      return n
  return fib_naive(n - 1) + fib_naive(n - 2)

def fib_memo(n, memo=None):
  if memo is None:
      memo = {}
  call_counts["memo"] += 1
  if n in memo:
      return memo[n]
  if n <= 1:
      return n
  result = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
  memo[n] = result
  return result

@functools.lru_cache(maxsize=None)
def fib_cached(n):
  call_counts["cached"] += 1
  if n <= 1:
      return n
  return fib_cached(n - 1) + fib_cached(n - 2)

N = 20

call_counts["naive"] = 0
result_naive = fib_naive(N)
print(f"fib_naive({N})   = {result_naive}  |  calls: {call_counts['naive']}")

call_counts["memo"] = 0
result_memo = fib_memo(N)
print(f"fib_memo({N})    = {result_memo}  |  calls: {call_counts['memo']}")

call_counts["cached"] = 0
result_cached = fib_cached(N)
print(f"fib_cached({N})  = {result_cached}  |  calls: {call_counts['cached']}")

For N = 20, fib_naive makes over 21 000 calls. Both memoised versions make exactly 21 calls — one per unique input from 0 to 20.

Why the memo dict works

fib_memo adds two lines to the naive version:

if n in memo:          # cache hit — return immediately
    return memo[n]
# ... compute ...
memo[n] = result       # cache miss — store before returning

The first time fib_memo(3) runs, it computes its answer and stores it in memo[3]. The second time — triggered by a different branch of the recursion — the if n in memo check returns immediately without recursing further. Every unique argument is computed at most once.

@lru_cache: the Pythonic shorthand

functools.lru_cache does the same thing with a decorator. The cache is keyed by the function's arguments. maxsize=None means the cache is unbounded — it keeps all entries rather than evicting the least recently used ones. For typical DP problems this is what you want.

Python 3.9+ also provides @functools.cache (no maxsize argument, always unbounded) as a cleaner alias for @lru_cache(maxsize=None). Both are correct for DP; use whichever your team prefers.

One subtlety: @lru_cache requires the function's arguments to be hashable. Lists are not hashable, so if your sub-problem state includes a list you must convert it to a tuple first, or switch to a manual dict.

The memo dict and default mutable arguments

Notice that fib_memo takes memo=None and initialises it inside the function, rather than memo={} in the default argument. Python evaluates default argument values once at function definition time. If you wrote def fib_memo(n, memo={}), the same dict would be shared across all top-level calls, which can cause subtle bugs in other contexts — though for Fibonacci it would accidentally work. Use None and initialise inside as the safe pattern.

Where to go next

Next: tabulation — the bottom-up alternative that fills a table from base cases upward, avoiding Python's recursion limit entirely and enabling space optimisations that top-down caching cannot.

Finished reading? Mark it complete to track your progress.

Three implementations side by side

Why the memo dict works

@lru_cache: the Pythonic shorthand

The memo dict and default mutable arguments

Where to go next

On this page