Why can a function that recurses only a dozen levels deep still overflow a thread's stack?

## Depth is only one factor of the product A stack overflow means the total reserved by all live frames exceeded the thread's limit. That total is: **bytes used = sum over live calls of that call's frame size** which, for a uniform recursion, is simply frame size times depth. Engineers instinctively read an overflow as 'too many calls' because most recursions have small frames and reach thousands of levels before they fail. When one frame is unusually fat, the same limit is hit at a depth so small it does not look like recursion at all. ## A worked budget Suppose each level of a recursive directory walk declares a 64 KiB local buffer - a scratch area for reading a block, or a fixed-size path array sized for the worst case. - One frame now costs about 65,536 bytes rather than the few dozen bytes of its bookkeeping. - A 1 MiB stack is 1,048,576 bytes, so **16** such frames fill it exactly, with nothing left for anything else. - At depth **12** the recursion has already reserved 786,432 bytes - **768 KiB**, three quarters of the budget - and the frames beneath it (the caller that started the walk, and whatever called that) take part of the remainder. So the walk dies somewhere around level 13 to 15, on a tree that is trivially shallow. Nothing about the recursion is wrong; the per-level price is. | | thin frames, great depth | fat frames, shallow depth | |---|---|---| | usual cause | deep input, or a base case never reached | a large local buffer or aggregate per call | | frames at the crash | thousands, often a short repeating cycle | a handful, each one distinct | | the arithmetic | limit divided by tens of bytes | limit divided by tens of kilobytes | | effective lever | reduce depth, or stop using frames | move the big local out of the frame | | bigger stack helps? | a constant factor, rarely enough | a constant factor, and usually cheaper to avoid | ## Why an untouched buffer still costs The prologue reserves the whole local area in one move, before the body decides how much of it to use. From the budget's point of view the address range is consumed the moment the stack pointer passes it, so a buffer you write four bytes into charges the same as one you fill. (Whether every reserved page ever becomes physically backed is a separate question from whether the limit was consumed - the limit is about how far the stack pointer travelled.) That is also why 'it only uses a bit of the buffer in practice' is not a defence. The reservation is unconditional and per call. ## How the crash reads 1. The failing stack is **short** - ten to twenty frames rather than thousands. 2. The frames are **distinct** and show real progress through the input, not the same cycle repeated. 3. The input that triggered it is unremarkable, which is what usually sends people hunting for the wrong bug. Taken together, those three say 'frame size', not 'depth'. Reading a short stack as proof that the stack was not exhausted is the classic wrong turn here. ## What to change - **Hoist the buffer.** Allocate it once before the recursion starts and pass a reference down. One buffer for the whole walk instead of one per level restores the per-level cost to tens of bytes. - **Size it for the case, not the worst imaginable case.** A fixed-size array sized for a pathological input is paid for at every level by every input. - **Split the function.** If only one branch needs the scratch area, move that branch into a separate function that the recursion calls and returns from, so the reservation lives only for that call rather than for the whole recursive path beneath it. - **Do not reach for a larger stack first.** It buys a constant factor at deployment time, on every thread that will ever run the code, to avoid a change that costs one parameter. - **Do not add threads.** More threads means more stacks, not a bigger one; the per-frame cost is unchanged and each thread carries the same ceiling.