What determines how deep recursion can go before the call stack overflows?

## The ceiling is bytes, not calls The common mental model — "there is a maximum number of recursive calls and I am under it" — is wrong in a way that matters. What exists is a **stack region**: a contiguous span of address space reserved for one execution context, sized when that context is created. Every call in progress occupies a frame inside it. So the usable depth is approximately: ``` max_depth ~= stack_region_bytes / average_frame_bytes ``` Both terms vary, which is why the same source code overflows at different depths in different circumstances. ## What makes a frame bigger or smaller Frame size is not a property of the language you think in; it is a property of what the call needs to keep: - **Number and size of parameters** — passing several large aggregates by value inflates every frame in the chain. - **Local variables**, especially a fixed-size scratch buffer declared inside the recursive body. A few kilobytes of locals per call can cut the tolerable depth by two or three orders of magnitude. - **Saved registers and frame/link pointers**, which the calling convention dictates. - **Alignment padding**, which rounds every frame up. - **Optimisation decisions**: an inlined or merged call may consume no frame at all, so an optimised build can survive input that the unoptimised build cannot. That asymmetry alone should stop you from treating an observed maximum depth as a contract. ## What makes the region bigger or smaller The region size is set per execution context at creation. A process's initial context, contexts created later for concurrent work, and contexts created by a pooling layer are frequently given different sizes, and those sizes are configurable. The practical consequence: the same recursion can succeed on one path through your system and abort on another, purely because the work was picked up on a context with a smaller region. "It worked when I ran it directly" is therefore not evidence of safety. ## Depth is charged across the whole chain Only the current chain of unfinished calls occupies the stack, but *all* of it does — the recursion is not measured in isolation. Two consequences that interviewers probe: - **Mutual recursion counts.** If `A` calls `B` calls `A`, the frames interleave on the one region; there is no per-procedure budget. Depth is the length of the combined chain, and the bytes are the sum of the mixed frame sizes. - **Non-recursive nesting counts.** A recursion entered from an already-deep call chain — layered frameworks, nested interceptors, deep composition — starts with much of the region already spent. The recursion did not change, but its headroom did. ## Tail position is not automatically free A call in **tail position** — the last thing the caller does, with nothing waiting after it returns — could in principle reuse the caller's frame instead of adding one, turning recursion into a loop with constant stack. But that only happens if the execution environment actually performs the transformation. Mainstream ecosystems made different calls here: some language standards mandate proper tail calls (Scheme is the canonical example, and Lua guarantees them), while the JVM and CPython deliberately do not, preferring complete stack traces and simpler debugging over the optimisation. So "I made it tail-recursive" is a claim about the runtime you are on, not a universal fix — and in the widely used case, the frames still accumulate. ## What happens at the moment of overflow The next frame does not fit. Depending on the environment, this is detected by a guard region the machine touches or by an explicit depth check, and the result is an abrupt termination of that execution context. The important property is that it is **discontinuous**: no gradual slowdown, no rising pressure metric, no partial result. Recovery is also unreliable in general, because the recovery path itself may need stack it does not have — treating overflow as an ordinary catchable condition and continuing is a design smell, not a mitigation. ## Why enlarging the region is a stopgap Doubling the region doubles the tolerable depth. If depth grows linearly with input, that doubles the tolerable input size — a constant factor against an unbounded quantity. It is a legitimate emergency lever that buys time, paired with an alarm; it is not an answer to "is this safe on input we do not control". The structural answers are to bound the depth (make it independent of input size) or to move the per-item state off the stack entirely. ## Estimating it in an interview You will not be asked for an exact number, and offering one is a mild red flag. What earns credit is the shape of the estimate: region size in the low megabytes, frames from tens of bytes to kilobytes depending on locals, hence a plausible depth of roughly ten thousand to a few hundred thousand for lean frames and dramatically less for fat ones — stated as an order of magnitude with the assumptions named.