skip to content

A memoized recursion over 200k log events overflows the stack in production — what went wrong?

level: seniorimportance: should knowfreq 42%

answer

  1. count frames, not cache entries
  2. what did the small test inputs hide
  3. how deep is the very first descent
  4. cache stops repeats, never the first visit
  5. the fix removes the stack entirely

basics

~20 s

The cache prevents repeated work, not depth. The first descent to a base case is one unbroken chain of pending calls as long as the event list, so recursion depth grows with the input while the state count stays modest. Small test inputs never reach the limit.

solid answer

~50 s

Memoization bounds the *number* of evaluations, not the *depth* of any single evaluation. Before any cache entry exists, the top-level call descends one state at a time toward the base case, so the depth is the length of the longest dependency chain — here proportional to the number of events, around 200,000 frames. The state count is irrelevant to that: a DP with 200k cheap states fits in memory comfortably and still exhausts a stack that holds a few thousand to a few tens of thousands of frames. It is a cliff, not a slowdown, and it is input-size dependent, which is exactly why a suite that runs a few hundred synthetic events stays green. The fix is to fill the states iteratively in dependency order — same recurrence, same asymptotic time, zero depth. Then add a test at production scale so the next depth regression fails in CI.

code

pseudocode · 10 lines
pseudocode
// best[i] = max value obtainable from event i onward
BEST(i):
    if i >= length(events): return 0
    if memo[i] != EMPTY: return memo[i]
    skip = BEST(i + 1)
    take = value(events[i]) + BEST(next_compatible[i])
    memo[i] = max(skip, take)
    return memo[i]
...
// entry point: BEST(0), with length(events) = 200000

go deeper

for a junior

Remember that caching results does not shorten the chain of pending calls; a recursion whose depth grows with input size can exhaust the stack even when the cached data is small.

for a middle

Explain the two independent quantities — number of states versus longest dependency chain — and show the iterative fill that eliminates depth while keeping the same recurrence and complexity.

for a senior

Diagnose it as a scale-dependent cliff invisible to small tests, rule out the cache and exponential blowup as causes, and land the fix plus a test at realistic input size.

for a principal

Turn one incident into a standing check: how the team reviews recursion whose depth tracks unbounded input, and when a depth bound is documented and asserted rather than removed.

## Two different quantities that both feel like "size" A memoized dynamic program has two independent size measures, and confusing them is the whole bug. - **State count** decides time and result memory: each state is evaluated at most once, so the total work is states multiplied by transition cost, and the cache holds one entry per computed state. - **Longest dependency chain** decides recursion depth: the top-level call cannot return until the call it made returns, and so on down to a base case. The cache only ever suppresses *repeat* visits. It cannot suppress the *first* visit to anything, and the first visit to the base case happens at the bottom of an unbroken chain of pending calls. In the fragment above, `BEST(0)` calls `BEST(1)` before it can do anything else, which calls `BEST(2)`, and so on: with 200,000 events the depth is essentially 200,000. Every one of those frames is still pending when the first cache write finally happens on the way back up. So the diagnosis is: **200,000 states is a small DP; 200,000 frames is not a small stack.** ## Why the tests passed Stack exhaustion is a threshold effect on the input length, not a gradual degradation. A suite that exercises a few hundred synthetic events sits three orders of magnitude below the cliff and reports a healthy green. Nothing in the code is wrong at that size — the same code that crashes is provably correct. Runtimes differ in exactly how the cliff is expressed: Python and several JavaScript engines enforce an explicit recursion-depth ceiling that trips in the low thousands, while the JVM and natively compiled C++ binaries simply run past the end of the thread's stack segment. Either way the limit is a fixed budget that the input can outgrow, and the crash arrives without warning at whatever scale production happens to hit first. This is why "it works on the sample input" is not evidence about recursion depth, and why a size-scaled test is the durable fix for the *class* of bug rather than this instance of it. ## What to do about it in the review **The default fix is the iterative fill.** Read the dependency direction off the recursion: `BEST(i)` reads only larger `i`, so the table is filled descending from the last index toward zero. Same recurrence, same states, same asymptotic time and result memory, and no stack at all. This is also the fix that scales: it has no depth limit to outgrow next quarter when the log doubles. **Raising the depth limit is a delay, not a fix.** It trades a crash at 200k for a crash at whatever the new ceiling implies, reserves more memory per worker thread, and buries the constraint in configuration where the next reader will not connect it to this recurrence. Accept it only as a deliberate stopgap on a dated ticket. **Warming the cache is a curiosity worth knowing.** You can iterate the states in dependency order and call the memoized procedure on each, so every top-level call finds its dependencies already cached and never descends more than one level. It works, and it preserves the readable recursive body — but at that point you have written the iterative loop anyway, and the iterative body is simpler than the loop plus the recursion. **Where recursion genuinely must stay** — because the state graph has no order you can defend — the depth becomes a constraint you own explicitly: bound it, document why the input cannot exceed it, and assert the bound rather than discovering it in production. ## The check to institutionalise Asked in a review, the useful question is not "is this recursive?" but **"how long is the longest dependency chain, in terms of the input, and what is the depth budget?"** If the chain grows with input size and the input is unbounded — a log, a stream, a user-supplied list — the recursive form is a latent outage regardless of how correct it is. Two artefacts make that durable: a test at or above the largest realistic input, and a comment on the recurrence stating the depth bound. Both survive the reviewer moving teams; a review comment does not. ## The wrong diagnoses to rule out fast Candidates often reach first for the cache: "the memo must be evicting", "the lookups degrade". Neither produces a stack overflow — a degraded cache produces slowness or extra work, never a depth failure. Nor is it an exponential blowup: exponential recomputation would have shown as a hang and a hot processor long before any crash, and the cache rules it out anyway. Depth is the only quantity here that is proportional to the input and independent of the state count.

  • Tests pass at 500 events and production runs 200k. How do you catch this class of bug earlier?
    Add a test at or above the largest realistic input for anything whose recursion depth grows with input size — it is cheap, since the DP itself is linear here. Pair it with a review habit: ask of any recursive traversal how long the longest dependency chain is in terms of the input, and whether that input is bounded by anything other than hope.
  • Can you keep the recursive form and still survive the depth?
    You can iterate the states in dependency order and call the memoized procedure on each, so no call ever descends more than one level. It works and preserves the readable body, but you have then written the iterative loop plus a recursion you no longer need. Raising the depth limit is worse: it moves the cliff instead of removing it.
  • Would this have been caught by looking at memory usage?
    Not usefully. The result cache is tiny — one entry per event — so heap graphs look healthy right up to the crash. The exhausted resource is a per-thread stack budget, which is a separate fixed allocation and does not show up as growing memory pressure in the usual dashboards.

saying these in an interview costs you the question

  • Blames the cache for evicting or degrading
  • Says the recursion must be exponential despite the memo
  • Concludes the state space is too large for memory
  • Treats raising the depth limit as the fix
  • Assumes a passing test suite rules out depth problems

context

resolving links…