A routine that recurses once per queued sensor reading crashes on large batches; what makes deep recursion fail?

seniorshould knowfreq 46%

answer

one live frame per outstanding call
a bounded region, not total memory
depth times frame size
the reservation is per thread
repeating cycle in the trace

basics

~20 s

Every live call holds a whole frame, and frames are pushed into one bounded region reserved for the running thread. Depth multiplied by frame size outgrows that region, and the overrun is detected as a fault rather than handled gracefully.

solid answer

~50 s

Each call in the chain keeps a frame alive — return address, saved caller state, parameters, locals, temporaries — and frames are only released as calls return. A recursion that descends once per reading therefore holds the whole batch's worth of frames at the deepest point. Those frames go into a bounded region reserved for the thread when it starts, so the limit is depth times frame size, not a call count: a routine with wide locals dies far shallower than one with two scalars, and the same depth can pass on one thread and fail on another because the reservations need not be equal. The failure is abrupt — the overrun is caught as a fault when the region's edge is touched — and the depth at which it happens shifts with input and with how much of the region the call chain had already consumed before the recursion began.

Each call in the chain keeps a frame alive — return address, saved caller state, parameters, locals, temporaries — and frames are only released as calls return. A recursion that descends once per reading therefore holds the whole batch's worth of frames at the deepest point. Those frames go into a **bounded region reserved for the thread when it starts**, so the limit is **depth times frame size**, not a call count: a routine with wide locals dies far shallower than one with two scalars, and the same depth can pass on one thread and fail on another because the reservations need not be equal. The failure is abrupt — the overrun is caught as a fault when the region's edge is touched — and the depth at which it happens shifts with input and with how much of the region the call chain had already consumed before the recursion began.

code

pseudocode · 8 lines

pseudocode

procedure ingestAll(pending)
    local scratch[4096]                // a fresh wide local in every frame
    if pending is empty then
        return
    handle(first of pending)
    ingestAll(rest of pending)         // previous frame still live below

// depth = number of readings; cost = depth x (scratch + parameters + saved state)

go deeper

for a junior

Recall that every call still running holds a frame and that frames pile up until calls return. Deep recursion means many live frames at once, in a space that is not unlimited.

for a middle

Explain the budget as depth times frame size against a bounded reservation, and say why a routine with wide locals fails much shallower than one with two counters at identical depth.

for a senior

Diagnose it from evidence: a repeating cycle in the trace, a depth that tracks input size, a thread-dependent failure. Name what drives the depth and what each frame carries before proposing anything.

for a principal

Set the rule. Decide where recursion over input-sized data is permitted at all, what bounds each recursive routine must document, and how work that grows with input is expected to carry its pending state instead.

A recursive routine is a routine that has not returned yet, several times over. Every call in the chain still holds its activation record — the return address, the saved caller state, its parameters, its locals and its temporaries — because a frame is released only when its call returns, and none of them has. At the deepest point of a recursion over a batch of readings, every one of those frames is simultaneously live.

What is actually exhausted

Not the machine's memory. Frames go into one bounded region reserved for the thread when that thread starts — a reservation made up front, independent of how much storage the program has available elsewhere. A program can fail this way with a very large amount of free storage, because the failure is about one thread's reservation, not about the total.

The budget is therefore:

achievable depth ≈ (region size − what the call chain already used) ÷ frame size

Three consequences follow directly, and they are what separates a real diagnosis from "it recursed too much":

Frame size matters as much as depth. Two routines recursing to the same depth do not both survive. A routine holding a wide scratch buffer as a local may take hundreds of times more per frame than one holding two counters, and dies hundreds of times shallower.
The limit is not a call count. There is no fixed number of permitted calls. Any constant you write down as "maximum depth" is a guess about frame size and about how much of the region was already spent before the recursion started.
Where the recursion begins matters. The same routine entered from a deep call chain has less of the region left than one entered near the top, so the same input can pass on one path and fail on another.

Why the same code fails on one thread and not another

Because the reservation is made per thread, and the sizes need not be equal. A program's initial thread, threads it creates itself, and threads created on its behalf to run callbacks or handlers may each get a different reservation. A recursion tuned until it "just fits" on one of them is a latent failure on any thread with a smaller one — a classic way for a routine that passed every test to fail only when the same work is driven from a different thread.

The failure signature

A crash rather than an exception you can meaningfully continue from. The overrun is detected when the region's edge is touched, and by then the program has already tried to build a frame it has no room for.
A depth that varies between runs and inputs rather than a constant, because the starting point and the exact frame contents vary.
A trace dominated by a repeating cycle of the same one or few frames. The cycle names the recursion; its length names the step.
Correlation with input size or shape — a deeper queue, a longer chain, a more nested structure — rather than with elapsed time or load.

Diagnosing it

Confirm the shape: is the deepest part of the trace a repeating cycle, and does the crashing input make that cycle longer? If yes, the depth is driven by data.
Establish what drives depth. One frame per reading, per node, per nesting level — say which, because that is the quantity you must bound.
Look at the frame, not just the count. Large locals, a record held by value in every frame, temporaries for a nested call — each multiplies straight into the budget.
Check which thread the work runs on, and whether the failing path enters the recursion from deeper in the call chain than the passing one.

Why it cannot simply be handled

Recovering needs somewhere to run the recovery, and the thing that ran out is the storage a call needs to run at all. Any handler is itself a call. That is why the sound approaches are preventive: make the depth a function of something you bound, shrink what each frame carries, or move the pending work into a data structure you allocate and size yourself rather than into the call chain — a change of control-flow shape, and a subject of its own.

The mental model to keep

Recursion spends a resource that ordinary iteration does not: one frame per outstanding call, reclaimed only on the way back out. That is fine when depth is bounded by something structural — the height of a balanced structure, a fixed number of stages — and it is a hazard the moment depth is proportional to the size of the input, because the input is the one thing you do not control. Ask of any recursive routine: what bounds the depth, and is that bound a property of the algorithm or a property of today's data?

A recursive routine is a routine that has not returned yet, several times over. Every call in the chain still holds its **activation record** — the return address, the saved caller state, its parameters, its locals and its temporaries — because a frame is released only when its call returns, and none of them has. At the deepest point of a recursion over a batch of readings, every one of those frames is simultaneously live. ## What is actually exhausted Not the machine's memory. Frames go into **one bounded region reserved for the thread when that thread starts** — a reservation made up front, independent of how much storage the program has available elsewhere. A program can fail this way with a very large amount of free storage, because the failure is about one thread's reservation, not about the total. The budget is therefore: > **achievable depth ≈ (region size − what the call chain already used) ÷ frame size** Three consequences follow directly, and they are what separates a real diagnosis from "it recursed too much": 1. **Frame size matters as much as depth.** Two routines recursing to the same depth do not both survive. A routine holding a wide scratch buffer as a local may take hundreds of times more per frame than one holding two counters, and dies hundreds of times shallower. 2. **The limit is not a call count.** There is no fixed number of permitted calls. Any constant you write down as "maximum depth" is a guess about frame size and about how much of the region was already spent before the recursion started. 3. **Where the recursion begins matters.** The same routine entered from a deep call chain has less of the region left than one entered near the top, so the same input can pass on one path and fail on another. ## Why the same code fails on one thread and not another Because the reservation is made per thread, and the sizes need not be equal. A program's initial thread, threads it creates itself, and threads created on its behalf to run callbacks or handlers may each get a different reservation. A recursion tuned until it "just fits" on one of them is a latent failure on any thread with a smaller one — a classic way for a routine that passed every test to fail only when the same work is driven from a different thread. ## The failure signature - A crash rather than an exception you can meaningfully continue from. The overrun is detected when the region's edge is touched, and by then the program has already tried to build a frame it has no room for. - A depth that **varies between runs and inputs** rather than a constant, because the starting point and the exact frame contents vary. - A trace dominated by a **repeating cycle** of the same one or few frames. The cycle names the recursion; its length names the step. - Correlation with **input size or shape** — a deeper queue, a longer chain, a more nested structure — rather than with elapsed time or load. ## Diagnosing it 1. Confirm the shape: is the deepest part of the trace a repeating cycle, and does the crashing input make that cycle longer? If yes, the depth is driven by data. 2. Establish what drives depth. One frame per reading, per node, per nesting level — say which, because that is the quantity you must bound. 3. Look at the frame, not just the count. Large locals, a record held by value in every frame, temporaries for a nested call — each multiplies straight into the budget. 4. Check which thread the work runs on, and whether the failing path enters the recursion from deeper in the call chain than the passing one. ## Why it cannot simply be handled Recovering needs somewhere to run the recovery, and the thing that ran out is the storage a call needs to run at all. Any handler is itself a call. That is why the sound approaches are preventive: make the depth a function of something you bound, shrink what each frame carries, or move the pending work into a data structure you allocate and size yourself rather than into the call chain — a change of control-flow shape, and a subject of its own. ## The mental model to keep Recursion spends a resource that ordinary iteration does not: one frame per outstanding call, reclaimed only on the way back out. That is fine when depth is bounded by something structural — the height of a balanced structure, a fixed number of stages — and it is a hazard the moment depth is proportional to the size of the input, because the input is the one thing you do not control. Ask of any recursive routine: *what bounds the depth, and is that bound a property of the algorithm or a property of today's data?*

What does the trace from such a crash tell you, beyond the fact that it recursed?
The repeating cycle of frames names the recursive step, and the length of one cycle tells you how many calls make up a single logical descent. The depth reached tells you roughly what the region divided by the frame size is, which is the number to compare against the depth your input actually demands.
Why is a fixed maximum-depth constant a fragile guard?
Because it encodes two things it cannot know: how large each frame is, and how much of the region the call chain had already consumed before the recursion started. The same constant is safe when entered near the top and unsafe when entered from a deep chain, and it silently becomes wrong when someone adds a local to the routine.
Why can a program fail this way while plenty of storage is still free?
Because frames go into a region reserved for the running thread when it started, and that reservation is fixed independently of what is free elsewhere. Exhausting it is a statement about one thread's budget, not about the program's total, which is why the crash can look inexplicable next to a healthy memory reading.

saying these in an interview costs you the question

Says deep recursion fails because the machine ran out of memory overall
Assumes the limit is a fixed number of calls, the same everywhere
Thinks the size of each frame does not affect the achievable depth
Believes the failure is graceful and can be caught and resumed reliably
Says every thread in a program gets the same stack reservation
Ignores where the recursion was entered from in the call chain

A routine that recurses once per queued sensor reading crashes on large batches; what makes deep recursion fail?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

What is actually exhausted

Why the same code fails on one thread and not another

The failure signature

Diagnosing it

Why it cannot simply be handled

The mental model to keep

▾common follow-ups3 questions

▾red flags6 flags

What is actually exhausted

Why the same code fails on one thread and not another

The failure signature

Diagnosing it

Why it cannot simply be handled

The mental model to keep

answer

go deeper