Memoization (top-down DP) — recursive + memo dict: Question bank

Definition Notation you'll see on this page (read first)

DP = Dynamic Programming — the paradigm of solving a problem by combining answers to smaller, overlapping subproblems and reusing (caching) each answer. Memoization is its top-down form.
Big-O notation — a way to describe how work grows as the input grows, ignoring constants. $O (1)$ = "constant, doesn't grow with $n$ " (a single dict lookup). $O (n)$ = "grows in a straight line with $n$ ". $O (2^{n})$ = "doubles each time $n$ grows by one — explodes". See the picture below and Time Complexity Analysis.
[!intuition], [!definition], [!mistake], [!recall] — these bracketed tokens are just Obsidian callout labels: they colour the box that follows (a hint box, a definition box, a warning box, a collapsible recall box). They are formatting, not maths — read them as the heading of the coloured box.
C-B-R-S — the mandatory order of a memoized function's four steps: Check the cache → hit the Base case → Recurse into subproblems → Store the answer before returning. ("Can Birds Really Sing?")

Two recursion trees — the intuition behind every answer below

Intuition What the cache table looks like as it fills

The memo dict is a lookup table state → answer. The first time we solve a state we write a row (a sticky note); every later request just reads that row in

O (1)

True or false — justify

Memoization always beats plain recursion.

False — it only helps when subproblems overlap (a node appears twice in the recursion tree). On merge sort the halves are always distinct, so the cache never gets a hit and you pay memory for nothing. That's Divide and Conquer, not DP (Dynamic Programming).

Memoization changes the answer a recursion computes.

False — it changes only the speed. The cached value is identical to what the recursion would recompute; you are trading recomputation for a stored lookup, never trading correctness.

Top-down and bottom-up DP have different time complexity.

False — same recurrence, same number of distinct states, same work per state, so the same big-O. They differ only in control flow (recursion vs iteration) and in which states get touched.

Memoization removes the risk of stack overflow.

False — it removes redundant calls, but the recursion still descends to the base case once, so depth can be

O (n)

. In Python the default recursion limit is only about 1000 frames, so a deep chain (e.g. fib(100000) without help) blows the Recursion stack even when fully memoized — see the edge-case note below.

Adding a cache turns any exponential algorithm polynomial.

False — only if the number of distinct states is polynomial. If the state itself is exponential (e.g. a subset of

n

items →

2^{n}

states), the cache is exponentially large and you gain nothing asymptotically.

@lru_cache is functionally equivalent to a manual memo dict.

Mostly true, with caveats — [[lru_cache decorator|lru_cache]] requires hashable arguments and can evict entries when maxsize is set. A hand-rolled dict never evicts, so results differ only if you rely on eviction or pass unhashable state.

If a function has optimal substructure it is automatically memoizable.

False — you need optimal substructure and overlapping subproblems. Optimal substructure alone (distinct subproblems) is just divide-and-conquer; the cache does no work.

The memo dict must be global to work.

False — it can be a parameter, a closure variable, or a decorator's hidden store. What matters is that the same cache is shared across the recursive calls of one top-level invocation.

Spot the error

def fib(n, memo={}): ... — what's wrong?

The default {} is created once at function-definition time and shared across every separate top-level call, so state leaks between independent invocations. Fix: memo=None then if memo is None: memo = {}.

A knapsack solver caches by index only while the recurrence depends on (index, capacity). What breaks?

Two calls with the same index but different capacity collide: the second reads the first's stale answer. The key must contain every variable that changes the result — here the tuple (index, capacity).

def f(n, memo=None):
    if memo is None: memo = {}
    if n < 2: return n
    return f(n-1, memo) + f(n-2, memo)

Why is this still exponential?

There is a base case and a memo is passed, but nothing is ever stored and there is no cache check. Without the read-and-write steps the dict is dead weight — it stays empty forever.

if n < 2: return n
if n in memo: return memo[n]

The base case is checked before the cache. Is that a bug?

Not a correctness bug for small base cases, but it's wasteful for them and a smell: convention is cache-check first (the C in C-B-R-S: Check → Base → Recurse → Store). The real danger is if base cases were expensive — you'd recompute them every time instead of caching.

Store-before-return: contrast the correct pattern with the pitfall.

# WRONG — value never saved: 'return' fires, the store line is unreachable
def f(n, memo):
    ...
    return f(n-1, memo) + f(n-2, memo)
    memo[n] = ...          # dead code, never runs
 
# RIGHT — compute, STORE, then return the stored value
def f(n, memo):
    ...
    memo[n] = f(n-1, memo) + f(n-2, memo)   # S: store first
    return memo[n]                          # then hand it back

::: The return in the WRONG version exits immediately, so the assignment below it is unreachable and the cache stays empty — you get exponential behaviour again. Always Store into memo before the return (the S in C-B-R-S).

A recursion stores memo[n] = f(n-1) + f(n-2) and then return f(n) recomputing the top call. Problem?

You store the value but then trigger a fresh recursion to return it instead of returning memo[n]. Return the stored value directly — otherwise you re-run the whole subtree once more.

Someone caches a function whose result depends on time.time(). Why is memoizing it wrong?

The function is not pure — its output depends on hidden external state not in the key. Memoization assumes "same inputs → same output"; once that breaks, cached values are silently wrong.

A grid solver keys the cache by r * COLS + c. Any risk?

Fine if COLS is fixed and c < COLS always — it's a valid injective flattening. It breaks the moment c can equal or exceed COLS, because then two different (r,c) pairs map to the same integer and collide.

Why questions

Why do we count distinct states rather than function calls for the time complexity?

Because after the first computation every repeated call is an

O (1)

(constant-time) dict lookup. Total time = (number of unique states) × (work per state), which is what actually gets computed. See Time Complexity Analysis.

Why must you store into the cache before returning, not after?

A line after return is unreachable dead code, so "return then store" never actually stores. The safe pattern is compute → memo[state] = ans → return memo[state], so the value is saved on the one path out. (See the WRONG/RIGHT snippet above.)

Why does memoization only compute states you "actually need," unlike tabulation?

Recursion is lazy: it descends from the goal and only visits subproblems reachable from it. Tabulation (Bottom-up DP) fills a whole table, possibly including states the answer never depends on.

Why is getting the base case value right called "the most error-prone part"?

Every answer is ultimately assembled from base cases. One wrong base value (e.g. W(0)=0 instead of 1) propagates upward and corrupts every result — the recurrence is correct but the foundation is rotten.

Why does the cache key need every parameter that affects the answer?

The key is the identity of a subproblem. If two genuinely different subproblems share a key, the second silently reads the first's answer. Missing a variable = false cache hits = wrong output that still runs fast.

Why doesn't Python's recursion depth shrink even after you add a cache?

The cache removes repeat calls (breadth), but the deepest single chain to a base case still stacks up frame by frame, and Python performs no tail-call optimization — it never reuses a frame for a tail recursive call. So depth stays

O (n)

and can hit the ~1000-frame limit.

Why is memoization considered a form of Dynamic Programming and not just an optimization trick?

Because it requires the two DP properties — optimal substructure and overlapping subproblems — and it systematically reuses subproblem answers. It's the top-down implementation of Dynamic Programming, the twin of tabulation.

Edge cases

What does the cache do when n = 0 or n = 1 in Fibonacci?

Nothing — those hit the base case and return immediately before any store, so the smallest inputs are never cached. Only

n \geq 2

get memoized. This is correct and intentional.

For Grid Unique Paths, why is the whole first row and first column the base case return 1?

Along an edge (r == 0 or c == 0) there is exactly one straight-line path — you can only keep going the single legal direction. No branching means one path, so the recursion must stop there.

What happens if you call a memoized function on an input below the base case, like fib(-3)?

With if n < 2: return n it returns -3 — garbage, because the recurrence was never defined for negatives. Memoization faithfully caches nonsense; you must guard the domain yourself.

fib(100000) in Python even with a perfect cache — what actually happens, and how do you fix it?

It raises RecursionError because the deepest chain exceeds Python's default limit of ~1000 frames — the cache helps time, not depth. Fixes: raise it with sys.setrecursionlimit(...), convert to an iterative bottom-up loop (no stack), or use an explicit stack. There is no tail-call optimization to lean on.

If the recursion has no repeated subproblems (all states distinct), what does the cache achieve?

Every lookup misses, so you pay the full recursion cost plus the memory and hashing overhead of the dict. Net effect: same time, worse constants. This is the divide-and-conquer case where memo hurts.

What is the space cost of memoized recursion, and why two terms?

O (distinct states)

for the cache plus

O (recursion depth)

for the live call stack. Even after caching, the deepest chain of pending calls occupies stack frames simultaneously — and without tail-call optimization that depth is not reduced.

Recall One-line self-test

If you can answer "what is the full state, and what does one wrong base value do to the tree above it" for any DP problem, you've internalized this page.

Connections

Parent (Hinglish)
Recursion · Dynamic Programming · Tabulation (Bottom-up DP)
Time Complexity Analysis · Divide and Conquer
Hash Maps / Dictionaries · lru_cache decorator