How do you estimate how deep a recursive call chain can go before it exhausts a thread's stack?
answer
- bytes, not number of calls
- stack size divided by frame size
- frame size is the lever you control
- one large local shrinks depth fast
- budget against worst-case input depth
basics
~20 sDivide the thread's stack size by the average frame size: a 1 MiB stack with 80-byte frames allows roughly 13,000 nested calls. Frame size is the lever - adding a 256-byte local buffer per frame cuts that to about 3,100.
solid answer
~50 sThe stack is a byte budget, not a call budget, so the estimate is `depth = stack size per thread / bytes per frame`. Both numbers are concrete: the stack size is fixed when the thread is created, and the frame cost is whatever the compiler reserved for the return address, saved registers, locals, spills and outgoing arguments. A 1 MiB stack (1,048,576 bytes) with 80-byte frames gives about 13,000 levels; add a 256-byte path buffer to each frame and the frame is about 336 bytes, so the same stack holds roughly 3,100 - a four-fold loss from one local array. Treat the result as an order of magnitude, take the largest frame in a mutually recursive cycle, and leave a wide margin, because the recursion does not start from an empty stack. If the worst-case depth follows data you do not control, the arithmetic says no stack size is safe.
go deeper
Remember the shape of the calculation: the stack is a fixed number of bytes, each nested call takes a slice, so depth is the budget divided by the slice size.
Do the division out loud with real numbers and name what makes up a frame. Show that adding one sizeable local per call cuts the safe depth by the same factor it grows the frame.
Turn the number into a decision for a running service: measure the true frame size, budget against the worst input with margin, and say when the recursive form should be abandoned instead of tuned.
Own the policy: where stack sizes are set, which inputs are allowed to determine depth, and why frame-size discipline in code beats a per-deployment stack knob that every future thread must get right.
## The arithmetic an interviewer is fishing for The limit on nesting is a **byte** limit, not a count of calls. The estimate is one division: **maximum depth = stack size for that thread / average bytes per frame** Both inputs are things you can obtain. A thread's stack size is a fixed number chosen when the thread is created; defaults differ widely between platforms, and most environments let you ask for a different size. The per-frame cost is whatever the compiler reserved for that function: return address, saved frame pointer, callee-saved registers, locals, spilled temporaries and outgoing argument space. Worked through: a thread with a **1 MiB** stack has 1,048,576 bytes. A recursive walk whose frames run about **80 bytes** each therefore reaches roughly **13,000** levels. Give every frame a 256-byte path buffer and the frame becomes about **336 bytes**, so the same stack now holds about **3,100** levels - one local array cost you a factor of four. | stack size | ~80-byte frames | ~336-byte frames | |---|---|---| | 256 KiB | ~3,300 levels | ~780 levels | | 1 MiB | ~13,000 levels | ~3,100 levels | | 8 MiB | ~105,000 levels | ~25,000 levels | The table is the real lesson: moving along a row (shrinking the frame) is usually cheaper and safer than moving down a column (buying stack), because the frame size is in your code while the stack size is a deployment knob that has to be right on every thread that ever runs the function. ## Where the frame size comes from - **Fixed overhead per call**: the return address, the saved frame pointer if one is kept, and the callee-saved registers the function touches. This is the part you cannot influence much. - **Locals the compiler cannot keep in registers** - anything whose address is taken, anything aggregate, anything still live across a nested call. - **Spills**, which grow with how many values are simultaneously live; a long function with a big working set spills more than a short one. - **Outgoing argument space** for the calls this function makes when the arguments exceed the registers reserved for them. - **Alignment padding**, which rounds the frame up to the platform's required boundary. ## Measuring rather than guessing 1. Take the address of the same local in two nested invocations and subtract: the difference is that frame's size plus any padding between frames. 2. Read the constant the prologue subtracts, in a disassembly or in whatever frame-size report the toolchain can be asked for. 3. Drive the recursion deliberately deeper and deeper until it fails, then divide the stack size by the depth reached - a crude but honest measurement of the real average. 4. In mutual recursion, budget the **cycle**: two functions of 80 and 300 bytes cost 380 bytes per round trip, not 190. ## Why the answer is an estimate - Frame sizes differ per call path; a recursion that sometimes takes a heavier branch has no single frame size. - The recursion does not begin at the bottom of the stack. Whatever called it is already there, and callbacks into your code stack further frames underneath and above. - An inlined call adds no frame at all, so frames on the stack and calls in the source are not the same count. - Some platforms grow the stack on demand up to its limit, so failure arrives at the limit rather than at whatever was committed initially. Because of all four, the number is a magnitude, not a guarantee. Budget against the worst input you are willing to accept, then leave a factor of several - not a few percent - between that and the computed ceiling. ## What you do with the number - If the computed ceiling is comfortably above the deepest input you accept, the recursive form is fine and you should say so with the number attached. - If the ceiling is close, shrink the frame first: hoist a large local out of the recursion and pass a reference down. That buys more depth than doubling the stack, and it costs nothing at deployment time. - If the input's depth is set by data you do not control, the arithmetic is telling you something structural: there is no stack size that makes the recursive form safe, so the depth must be bounded explicitly or the walk must stop using frames as its storage. - Write the assumption down next to the recursion. A later change that adds one array-shaped local can quietly divide the safe depth by four, and nothing in a build will point at it.
- How do you measure a real frame size rather than guessing one?Compare the address of the same local in two nested invocations - the difference is the frame plus padding - or read the constant the prologue subtracts from the stack pointer. Then take the largest frame in the recursive cycle rather than the mean, because the worst case is what overflows.
- Why budget against the worst-case input depth with a wide margin instead of the deepest depth you have observed?The deepest input seen so far is not the deepest one that will arrive, and your recursion never starts from an empty stack: the callers beneath it and any callbacks above it consume part of the same budget. A factor of several keeps a heavier call path or a slightly fatter frame from turning a safe design into a crash.
- Two mutually recursive functions alternate, one with an 80-byte frame and one with a 300-byte frame. What is the per-level cost?Budget per cycle, not per call: each round trip consumes 380 bytes, so a 1 MiB stack allows roughly 2,750 cycles, about 5,500 individual calls. Averaging the two frame sizes overstates the safe depth whenever the alternation is fixed.
saying these in an interview costs you the question
- Quotes a universal maximum recursion depth independent of frame and stack size
- Thinks the limit counts calls rather than bytes per frame times depth
- Assumes every frame in the recursion costs the same as the smallest one
- Believes raising the stack size fixes recursion whose depth follows untrusted input
- Ignores the frames already on the stack beneath the recursive entry point