Memoized recursion vs a bottom-up DP table: what actually differs between them?
answer
- same recurrence, two evaluation orders
- who decides which state is computed next
- one uses the call stack, one a loop
- does either visit unreachable states
- asymptotics match, constants and depth do not
basics
~20 sBoth evaluate the same recurrence at the same asymptotic cost. Memoization recurses from the goal downward, caching answers on demand and touching only states it can reach. Tabulation fills every state in an order you choose, using no call stack.
solid answer
~50 sThey are two evaluation orders for one recurrence, not two algorithms. Top-down asks for the goal state and lets the dependency graph decide what gets computed, caching each answer the first time it is produced; bottom-up picks an explicit order over the state space and fills it. When every state is reachable, both do `states x transition cost` work and store one result per state, so the asymptotic time and memory match. The real differences are elsewhere: recursion spends call-stack depth equal to the longest dependency chain, which is a hard cliff rather than a slowdown; memoization touches only the states reachable from the goal, which matters when most of the table is unreachable; tabulation has no per-call overhead, walks memory in a predictable pattern, and exposes the fill order you need for later memory tricks.
go deeper
Be ready to say in plain words that both forms compute the same recurrence with the same big-O, and name two concrete differences: recursion uses the call stack, and a table computes every cell whether or not it is needed.
Explain the mechanics: how the dependency graph orders a top-down run implicitly, why a bottom-up fill needs an explicit order, and how each form represents "not computed yet".
Show you pick by workload rather than taste. Talk about dependency-chain depth on real input sizes, the reachable fraction of the state space, and per-state overhead when the transition is cheap.
Own the consistency call: which form your codebase defaults to, when the clearer top-down version is worth its overhead, and what evidence would justify rewriting a working memoized path as a table.
## One recurrence, two evaluation orders A dynamic program is three things: a **state space** (the set of subproblems), a **recurrence** expressing one state's answer in terms of other states, and **base cases** that need no recurrence. Nothing in that definition says how the states get evaluated. Memoization and tabulation are the two standard answers to that one remaining question. **Top-down memoization** writes the recurrence literally as a recursive procedure and puts a cache in front of it. Asked for a state, it checks the cache; on a miss, it recursively asks for exactly the states the recurrence names, combines them, stores the result, and returns it. The evaluation order is chosen for you by the dependency graph itself: a state is computed only after everything it depends on has been. **Bottom-up tabulation** allocates the table up front, seeds the base cases, and walks the states in an order you have chosen so that every cell's dependencies are already final when that cell is written. There is no cache lookup and no recursion — reading `table[j]` is reading a slot you have promised yourself is done. ## What is identical - **The answers.** Same recurrence, same results, cell for cell. - **The asymptotic time**, when every state is reachable: number of states multiplied by the cost of one transition. Neither form changes the recurrence, so neither can change its complexity class. - **The result memory**, to within constant factors: one stored answer per computed state. This is the point most candidates fumble. "Bottom-up is faster" is not an asymptotic claim; at best it is a constant-factor claim, and it is not always true. ## What genuinely differs | | Top-down memoization | Bottom-up tabulation | |---|---|---| | Who fixes the evaluation order | the dependency graph, implicitly | you, explicitly, and you must be right | | Call-stack use | depth of the longest dependency chain | none | | States computed | only those reachable from the goal | every cell in the declared range | | Per-state overhead | a call plus a cache probe | a loop step and an indexed write | | Memory access pattern | scattered, in discovery order | sequential, cache-friendly | | Ease of getting right | mirrors the recurrence; hard to misorder | needs an ordering argument before it works | Two consequences deserve naming. **Stack depth is not the same quantity as state count.** A memoized run over a few thousand states can still descend a few thousand frames before the first base case returns, because the cache only prevents *repeat* work, never the first unbroken descent. A state space that fits comfortably in memory can therefore still exhaust a call stack. **"Not yet computed" needs a representation.** A dense table typically initialises to a sentinel, and the classic bug is a sentinel that is also a legitimate answer — zero cost, or an empty result — so a genuine answer is mistaken for an empty cell and recomputed or, worse, overwritten. A keyed cache sidesteps this by testing presence rather than value; a table needs either an impossible sentinel or a parallel presence flag. ## Choosing between them Reach for **top-down** when the recurrence is awkward to order (states that skip around, transitions that jump by data-dependent amounts), when the reachable fraction of the state space is small, or simply when you are deriving the solution and want the code to look like the recurrence you just wrote on the board. Reach for **bottom-up** when the state space is dense and you will visit nearly all of it anyway, when the per-state work is tiny and call overhead would dominate, when the dependency chain is long enough that recursion depth becomes a risk, or when you intend to shrink memory by keeping only the most recent slice of the table — that trick needs a known fill order, which only the iterative form gives you. In a real interview, writing the memoized version first is usually the stronger move: it is the shortest path from recurrence to a correct solution, and converting it to a table afterwards is a mechanical follow-up you can offer yourself before being asked. ## The wrong answer to avoid "Tabulation is better because recursion is slow." It states a constant-factor preference as if it were a complexity result, ignores that memoization can do strictly less work on a sparse state space, and skips the one thing that actually differs in kind — the stack.
- Which form would you write first under interview time pressure, and why?Top-down. It is a direct transcription of the recurrence, so it needs no ordering argument and there is less to get wrong while a clock is running. Once it is correct and the complexity is stated, offer the conversion to a table as the natural next step — that sequencing also shows you know they are the same solution.
- Is the memory usage really the same in both forms?Same order — one entry per computed state — but not the same shape. A keyed cache stores only visited states and pays per-entry overhead; a dense table pays for every cell up front whether or not it is used. On top of that, the recursive form adds stack proportional to the longest dependency chain, which the iterative form does not have at all.
- How do you distinguish an uncomputed cell from a genuine answer that happens to equal your initial value?Either pick a sentinel that can never be a legitimate answer for this recurrence, or keep a separate presence flag alongside the value. Initialising a cost table to zero and treating zero as "empty" is the standard bug: a real answer of zero is then recomputed forever, or a base case is silently discarded.
Memoization is answering a question by phoning whoever you need and writing each answer down as it comes back. Tabulation is filling a form from the first line to the last, having worked out in advance which lines feed which.
saying these in an interview costs you the question
- Claims tabulation is asymptotically faster than memoization
- Treats memoization and DP as two different algorithms
- Says recursion always overflows the stack, so never use it
- Assumes a bottom-up fill order needs no justification
- Cannot name a single case where top-down does less work