A payroll routine recursing down a long management chain exhausts the call stack — what does each nested call push onto it?
answer
- one record per active call
- return address and saved caller state
- locals live inside the frame
- depth multiplied by frame size
- tail position may reuse the frame
basics
~20 sEach nested call pushes an activation record: the return address, the saved caller bookkeeping, the parameter copies and the routine's local variables. Stack use is call depth multiplied by frame size, so a long chain exhausts the region.
solid answer
~40 sEvery active call owns one **activation record** (a stack frame) holding the return address, the saved caller state needed to unwind, the parameters as the calling convention delivered them, and the routine's locals and temporaries. Frames are pushed on call and popped on return, which is exactly why locals have automatic lifetime. Total usage is **depth multiplied by frame size**, so both sides matter: a chain a hundred thousand links long will exhaust the region, and so will a shallower recursion whose routine holds a large local buffer. The fixes follow from the formula — bound the depth, shrink the frame, or convert the walk into a loop with an explicit worklist that lives outside the stack.
code
pseudocode · 14 linesfunction payChain(employee)
set bonus = computeBonus(employee) // local: lives in this frame
if employee.manager is none
return bonus
return bonus + payChain(employee.manager) // addition is still pending
// the same walk, one frame, state moved into locals of a loop
function payChainIterative(employee)
set total = 0
set current = employee
while current is not none
set total = total + computeBonus(current)
set current = current.manager
return totalgo deeper
Be able to say that each active call gets its own block of storage for its parameters and locals, that the block goes away when the call returns, and that too many nested calls run the region out.
Explain the frame contents and the depth-times-size formula, and use it to diagnose: a shallow recursion can still exhaust the stack if each frame carries a large local.
Show the fix path in order — bound the depth, restructure the walk with an explicit worklist you can size, shrink the frame — and say why relying on frame reuse in tail position is the least portable of them.
Own the limit as a system property: what depth the workload can produce at its worst input, whether the failure is detected or fatal, and whether recursion over unbounded external data is allowed in this codebase at all.
## What one call costs The call stack is the runtime structure that makes subroutines work at all. Calling a routine pushes an **activation record** — one frame per *active* call — and returning pops it. A frame typically holds: - the **return address**: where execution resumes in the caller; - **saved caller state**: the previous frame pointer and whichever registers the calling convention makes the callee preserve; - the **parameters**, laid out as the convention dictates (copies for by-value arguments, locations for by-reference ones); - the routine's **local variables** and compiler temporaries; - often, space for the **outgoing arguments** of calls this routine will itself make. The sizes and the order are a matter of convention and differ between implementations, but the contents are the same everywhere, because they are what a call needs in order to return. ## Why depth is only half the story Stack consumption is **depth times frame size**. Engineers reach for depth first and forget the multiplier: | What grows | Effect on the total | Typical cause | |---|---|---| | Call depth | linear | recursion over a long chain, deep layering | | Frame size | linear | many locals, a large fixed-size local buffer, large by-value parameters | | Both together | multiplicative | a recursive routine that also copies an aggregate per call | So a recursion a thousand deep with a tiny frame is harmless, while a recursion two hundred deep that copies a large record per call may not be. If n is the length of the management chain, a recursive walk is O(n) in stack space; the iterative version below is O(1). ## The lifetime rule you get for free Because the frame is popped on return, every local in it dies at that moment. This is the automatic-lifetime rule procedural code relies on: no allocation call, no release call, no chance of leaking a local. The price is the mirror-image hazard — a routine that returns a reference to one of its own locals hands back storage that no longer exists. Whether that is a compile error, a checked error or silent corruption is exactly the kind of thing languages differ on, and the mechanism is the same in all of them. ## When recursion has to become iteration The conversion is mechanical once you see what the frame was holding: 1. Name the state the recursion was keeping per level — in a chain walk, usually just "where I am" and "what I have accumulated". 2. Move it into local variables of a loop, or into an explicit worklist structure for a walk that branches. 3. Replace the recursive call with either advancing the current position (a linear chain) or pushing onto the worklist (a branching walk). The state does not disappear; it moves out of the stack region, where the size limit is fixed and small, into a region you control and can grow. That relocation is the whole benefit, and it is worth saying explicitly in an interview, because "I rewrote it as a loop so it uses no memory" is wrong. ## Tail position, stated carefully A call is in **tail position** when its result is the caller's result with nothing left to do afterwards. Where a call is in tail position, an implementation *may* reuse the current frame instead of pushing a new one, turning the recursion into a loop. Two honest qualifications belong in the answer: - it applies only to calls genuinely in tail position — a recursive call whose result is then added to something is not one, because the addition is still pending and needs the frame; - implementations differ: some guarantee the elision, some do it opportunistically, some never do it, and some require the routine to be marked. Do not assume it. That is why the honest engineering answer to a stack exhaustion is first to bound the depth or restructure the walk, and only then to rely on frame reuse.
- Why is the recursive version above not eligible for frame reuse?Its recursive call is not in tail position. The result of the call is added to `bonus` before being returned, so the addition is still pending when the call runs, and the frame holding `bonus` must survive until the call comes back. Rewriting it to pass a running total down as a parameter would put the call in tail position — which some implementations exploit and others do not.
- The recursion is replaced by a loop with an explicit worklist. What actually changed?The per-level state moved out of the stack region into a structure you allocate and control. Nothing became free: a branching walk still holds one entry per pending branch. What you gained is a size limit you can choose and a failure you can detect and report, instead of a fixed, small region whose exhaustion aborts the routine from underneath you.
- Why does returning a reference to a local variable break?The local lives in the activation record, and the record is popped at return, so the storage the reference names is no longer the routine's. Anything the runtime does next may reuse it. The same automatic lifetime that frees you from releasing locals is what makes a reference to one invalid the instant the routine returns.
saying these in an interview costs you the question
- Says the stack stores the routine's code rather than its per-call data
- Thinks stack depth is limited by total available memory
- Believes a local variable survives after its routine returns
- Claims every recursive call can reuse a single frame
- Says converting recursion to a loop removes the per-level state