Memoization

coreCommon atGoogleAmazonMetaAnthropicRead firstRecursionHash mapsPractise in the Sandbox →

Memoization stores the result of a function call in a cache keyed by its arguments, and returns the stored value on the next call with the same arguments. Applied to a recursive solution with overlapping subproblems, it turns exponential time into (number of distinct states) × (work per state). It’s top-down DP: same recurrence as the bottom-up table, filled on demand.

The idea in plain words

fib(5) calls fib(4) and fib(3). But fib(4) also calls fib(3). And both call fib(2), over and over. The recursion tree doubles at every level even though there are only six different questions (fib(0) to fib(5)).

Memoization is the obvious fix once you see it: write down every answer the first time you compute it, and look it up before computing again. The recursion tree collapses into a chain.

Three requirements:

• Pure function. Same arguments, same result, no side effects that matter. Caching a function that reads a clock or a mutable global gives stale answers.
• Hashable key. The cache key must capture every argument that affects the result.
• Overlap. If subproblems never repeat (e.g. merge sort), caching only adds overhead.

See it

Start with the cache off: yellow nodes are subproblems already solved on another branch. Then turn it on and watch whole subtrees disappear into single cache hits.

fib(n): the recursion tree, before and after caching

step through

calls1

cache hits0

depth1

current callreturnedrepeated subproblem

Call fib(5): it needs fib(4) and fib(3).

↺◀▶ Play▶1 / 31

The gap grows exponentially. Drag n:

Calls made by fib(n)

drag the slider

n = 25

Plain recursion

242,785

Memoized

49

Bars use a log scale, otherwise the memoized bar would be invisible. Plain recursion makes 2·F(n+1) − 1 calls; with a cache it's 2n − 1. At n = 45 that's about 3.7 billion calls against 89.

When to reach for it

The situation…	Why memoization fits
You have a correct but slow recursive solution	Add a cache; often the fastest route to an accepted answer.
The recursion has a few small integer/string arguments	They make a clean cache key; the state space is their product.
Only a fraction of states are reachable	Top-down visits only what’s needed; bottom-up fills everything.
The fill order for a bottom-up table is awkward (trees, DAGs, intervals)	Recursion discovers the order for you.
Search / game trees with transpositions (same position via different moves)	Cache by position.

How it works

1. Base cases first, so they never touch the cache.
2. Look up the key. Return the cached value if present.
3. Compute from recursive calls, store, then return.

Fibonacci three ways: hand-written cache, the standard library decorator, and the bottom-up loop it’s equivalent to.

Python

fib.py

from functools import cache


def fib_memo(n: int, memo: dict[int, int] | None = None) -> int:
    """Top-down: plain recursion plus a dictionary of answers already known."""
    if memo is None:
        memo = {}
    if n < 2:
        return n                         # 1. base case
    if n in memo:
        return memo[n]                   # 2. seen before: O(1)
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)  # 3. compute once, store
    return memo[n]


@cache                                   # the stdlib does steps 2-3 for you
def fib_cached(n: int) -> int:
    return n if n < 2 else fib_cached(n - 1) + fib_cached(n - 2)


def fib_bottom_up(n: int) -> int:
    """Bottom-up: same recurrence, smallest subproblems first, no recursion depth limit."""
    a, b = 0, 1                          # fib(0), fib(1)
    for _ in range(n):
        a, b = b, a + b
    return a


if __name__ == "__main__":
    assert fib_memo(50) == fib_cached(50) == fib_bottom_up(50) == 12586269025
    assert [fib_bottom_up(i) for i in range(8)] == [0, 1, 1, 2, 3, 5, 8, 13]
    assert fib_bottom_up(5000) > 0       # fine; fib_memo(5000) would hit the recursion limit
    print("ok")

TypeScript

fib.ts

import assert from "node:assert/strict";

/** Top-down: plain recursion plus a Map of answers already known. */
export function fibMemo(n: number, memo: Map<number, bigint> = new Map()): bigint {
  if (n < 2) return BigInt(n); // 1. base case
  const hit = memo.get(n);
  if (hit !== undefined) return hit; // 2. seen before: O(1). (0n is falsy, so test undefined)
  const v = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); // 3. compute once, store
  memo.set(n, v);
  return v;
}

/** Bottom-up: same recurrence, smallest subproblems first, no recursion depth limit. */
export function fibBottomUp(n: number): bigint {
  let a = 0n, b = 1n; // fib(0), fib(1)
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

assert.equal(fibMemo(50), 12586269025n);
assert.equal(fibBottomUp(50), 12586269025n);
assert.deepEqual([0, 1, 2, 3, 4, 5, 6, 7].map(fibBottomUp), [0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n]);
assert.ok(fibBottomUp(5000) > 0n); // numbers beyond 2^53 need BigInt in JS
console.log("ok");

C#

fib.cs

// Top-down: plain recursion plus a dictionary of answers already known.
static long FibMemo(int n, Dictionary<int, long> memo)
{
    if (n < 2) return n;                                   // 1. base case
    if (memo.TryGetValue(n, out long hit)) return hit;     // 2. seen before: O(1)
    long v = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);  // 3. compute once, store
    memo[n] = v;
    return v;
}

// Bottom-up: same recurrence, smallest subproblems first, no recursion depth limit.
static long FibBottomUp(int n)
{
    long a = 0, b = 1;                                     // fib(0), fib(1)
    for (int i = 0; i < n; i++) (a, b) = (b, a + b);
    return a;
}

if (FibMemo(50, new()) != 12586269025L) throw new Exception("memo fib(50)");
if (FibBottomUp(50) != 12586269025L) throw new Exception("bottom-up fib(50)");
long[] first = [0, 1, 1, 2, 3, 5, 8, 13];
for (int i = 0; i < first.Length; i++)
    if (FibBottomUp(i) != first[i]) throw new Exception($"fib({i})");
Console.WriteLine("ok");                                   // fib(93) is the last that fits in a long

With more than one argument, the key is the tuple of all of them. Python and C# hash tuples by value; JavaScript Map compares object keys by identity, so encode the tuple as a string or a number.

Python

binomial.py

def binomial(n: int, k: int, memo: dict[tuple[int, int], int] | None = None) -> int:
    """C(n, k) by Pascal's rule. The cache key is the full set of arguments."""
    if memo is None:
        memo = {}
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1                                  # 1. base cases: edges of the triangle
    key = (n, k)                                  # 2. key = every argument that changes the answer
    if key not in memo:
        memo[key] = binomial(n - 1, k - 1, memo) + binomial(n - 1, k, memo)  # 3. Pascal
    return memo[key]


if __name__ == "__main__":
    memo: dict[tuple[int, int], int] = {}
    assert binomial(5, 2, memo) == 10
    assert binomial(30, 15, memo) == 155117520   # about 3 * 10^8 calls without the memo
    assert len(memo) <= 30 * 15                   # at most one entry per (n, k)
    assert binomial(4, 7) == 0
    print("ok")

TypeScript

binomial.ts

import assert from "node:assert/strict";

/** C(n, k) by Pascal's rule. The cache key is the full set of arguments. */
export function binomial(n: number, k: number, memo: Map<string, number> = new Map()): number {
  if (k < 0 || k > n) return 0;
  if (k === 0 || k === n) return 1; // 1. base cases: edges of the triangle
  // 2. key = every argument that changes the answer. Arrays can't be Map keys by value,
  //    so encode the pair as a string (or use n * BIG + k).
  const key = `${n},${k}`;
  let v = memo.get(key);
  if (v === undefined) {
    v = binomial(n - 1, k - 1, memo) + binomial(n - 1, k, memo); // 3. Pascal
    memo.set(key, v);
  }
  return v;
}

const memo = new Map<string, number>();
assert.equal(binomial(5, 2, memo), 10);
assert.equal(binomial(30, 15, memo), 155117520); // about 3 * 10^8 calls without the memo
assert.ok(memo.size <= 30 * 15); // at most one entry per (n, k)
assert.equal(binomial(4, 7), 0);
console.log("ok");

C#

binomial.cs

// C(n, k) by Pascal's rule. The cache key is the full set of arguments.
static long Binomial(int n, int k, Dictionary<(int, int), long> memo)
{
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;               // 1. base cases: edges of the triangle
    var key = (n, k);                             // 2. value tuples hash and compare by value
    if (!memo.TryGetValue(key, out long v))
    {
        v = Binomial(n - 1, k - 1, memo) + Binomial(n - 1, k, memo); // 3. Pascal
        memo[key] = v;
    }
    return v;
}

var memo = new Dictionary<(int, int), long>();
if (Binomial(5, 2, memo) != 10) throw new Exception("expected 10");
if (Binomial(30, 15, memo) != 155117520) throw new Exception("expected 155117520");
if (memo.Count > 30 * 15) throw new Exception("one entry per (n, k)");
if (Binomial(4, 7, new()) != 0) throw new Exception("expected 0");
Console.WriteLine("ok");

Top-down vs bottom-up

	Top-down (memoization)	Bottom-up (tabulation)
Code shape	Recursion + cache	Loops over a table
Order of evaluation	Discovered automatically	You must choose it
States computed	Only reachable ones	All of them
Overhead	Function calls + hashing	Array indexing
Stack depth	Up to the longest dependency chain (can overflow)	None
Space optimisation (keep 2 rows)	Hard	Easy
Best when	Sparse or awkward state spaces; prototyping	Dense, regular tables; tight limits

Recursion limits

Python’s default limit is about 1,000 frames (sys.getrecursionlimit()), and raising it with sys.setrecursionlimit risks a hard crash. JavaScript and .NET stacks are larger but still finite. For chains longer than a few thousand, convert to bottom-up or an explicit stack.

What it costs

	Time	Space
Plain recursion with overlap (Fibonacci)	O(φⁿ) ≈ O(1.6ⁿ)	O(n) stack
Memoized	O(states × work per state): O(n) for Fibonacci	O(states) cache + O(depth) stack
Bottom-up equivalent	Same	Same table, or less with rolling rows

A useful check: count the distinct argument combinations (the state space). For f(i, j) with i < n and j < m, that’s n · m states. Multiply by the loop inside each call. That’s your bound, regardless of how scary the recursion looks.

Variations you’ll meet

• Language helpers. Python: functools.cache (unbounded) and functools.lru_cache(maxsize=…). Arguments must be hashable, so pass tuples, not lists. JS/TS: no built-in; write a Map. C#: Dictionary<TKey, TValue> with a value-tuple key; ConcurrentDictionary.GetOrAdd for thread-safe caches.
• Bounded caches. When memory matters, evict least-recently-used entries. That’s the bridge from algorithmic memoization to caching and eviction in systems.
• Memoizing on objects. Key by a stable id or an immutable value, not by object identity (which defeats sharing) or by a mutable object (whose hash can change).
• Cache on the instance. Class methods that memoize should keep the cache per instance (or clear it), or results leak between inputs.
• Memoized DFS on graphs. Fine on DAGs; on graphs with cycles you need a “visiting” mark to avoid infinite recursion, and the answer may not be well defined.

Pitfalls

• Incomplete key. If the result depends on an argument (or a global) that isn’t in the key, different calls collide. Classic: memoizing dfs(i) when the answer also depends on remaining.
• Mutable default cache in Python: def f(n, memo={}) shares one dict across all calls forever. Use None and create it inside, or @cache.
• Unhashable arguments. Lists and dicts can’t be Python dict keys. Convert to tuples or frozensets.
• JS object keys. map.set([1, 2], v) then map.get([1, 2]) is undefined: different array objects.
• Falsy cached values. if (memo.get(k)) misses cached 0. Test !== undefined or has.
• Caching across test cases. A module-level @cache keeps results between unrelated inputs that share argument values. Clear it (f.cache_clear()) or scope the cache.
• Stack overflow on deep chains (see above).

In the interview

• Write the plain recursion first, then say: “f(i, j) is called with the same arguments from many places, and there are only n·m distinct pairs, so caching makes it O(n·m).”
• Name the key explicitly and check that it includes everything the result depends on.
• Mention the stack depth limit and offer to convert to bottom-up if inputs are large.
• Expect: “what’s the space?”, “convert it to iterative”, “can you reduce memory?”, “what if this cache is shared by many threads or must be bounded?” (a design question: LRU, TTL, locking).

Check yourself

Check yourself

pick one

A recursive function f(i, remaining) is memoized with a dictionary keyed only by i. What happens?

AIt is just slowerBIt can return wrong answers: calls with the same i but different remaining share one cached resultCIt raises an error

Check yourself

pick one

A memoized function has arguments i in [0, 1000) and j in [0, 1000), and each call does a loop of length 1000. What's the time bound?

AO(10⁶)BO(10⁹)CExponential, because it is recursive

Check yourself

pick one

In TypeScript: `const memo = new Map<number[], number>(); memo.set([2, 3], 7); memo.get([2, 3])` returns…

A7BundefinedCA type error

Practice on your own

Classic exercises (not gym questions):

• Count the ways to climb n stairs with steps of 1, 2 or 3, top-down.
• Number of paths in an m×n grid from the top-left corner, top-down, then compare with the bottom-up version.
• Can the first player win a game where players alternately take 1-3 stones and the one who takes the last wins? (memoize on stones left)
• Count binary trees with n nodes (Catalan numbers) via memoized recursion.
• Longest path in a DAG with memoized DFS.

Go deeper

• Python docs: functools.cache and functools.lru_cache.
• Introduction to Algorithms (CLRS), §15.3 “Elements of dynamic programming” (§14.3 in the 4th edition), the memoized version of the rod-cutting and matrix-chain recurrences.
• Jeff Erickson, Algorithms, ch. 3 “Dynamic Programming”: “memoization is not dynamic programming” and why order matters.
• .NET docs: ConcurrentDictionary<TKey,TValue>.GetOrAdd and its caveat that the value factory can run more than once.

Related

RecursionBase cases, call stacks and recursion trees.

Dynamic programming: 1DThe bottom-up version of the same idea.

Caching and evictionBounded caches: LRU, LFU and friends.

BacktrackingWhen subproblems don't overlap, there's nothing to cache.