Stack Overflow

Each call to recurse executes a call (8 bytes for the return address) and a prologue that reserves its frame — say 32–64 bytes for a trivial function, kilobytes for one with local arrays. Nothing returns, so nothing is popped, and the stack pointer marches towards lower addresses at a rate of one frame per call. At 48 bytes per frame, an 8 MB stack holds about 170,000 frames; at 4 kB per frame, about 2,000. Both take well under a millisecond to exhaust.

The stack does not "run out" by hitting the heap. The region is placed at the top of the address space with an unmapped gap below it, and the kernel grows the mapping on demand as the stack pointer descends — up to a limit. That limit is the stack size: on Linux the main thread’s limit is ulimit -s, 8 MB by default; on Windows it is set in the executable header, 1 MB by default; on macOS the main thread gets 8 MB. Threads other than the main one get a stack allocated by the threading library — glibc’s pthread_create defaults to the ulimit -s value (8 MB), macOS gives secondary threads 512 kB, Windows gives them 1 MB, the JVM 1 MB (-Xss), and Go gives goroutines a few kilobytes that grow by copying the stack, which is why Go recursion rarely overflows.

Below the maximum extent of the stack sits a guard page (or several): a page that is deliberately left unmapped or mapped with no permissions, so that the first access beyond the limit is a page fault the kernel cannot satisfy. That fault is the detection mechanism — there is no counter, no check on each call. The kernel’s page-fault handler sees an address just below the stack mapping, refuses to grow it further, and delivers SIGSEGV (User Mode vs Kernel Mode, Page Faults). The signal handler, if any, needs a stack to run on and the stack is what just failed, which is why runtimes that want to report overflows nicely register an alternate signal stack (sigaltstack) in advance.

The guard page works only if every frame touches the stack within one page of the previous one. A function with a 1 MB local array could skip the guard page entirely and land in whatever mapping lies below — a silent corruption instead of a crash. This is why compilers emit stack probes for large frames (touching every page of the frame in order, -fstack-clash-protection, always on in MSVC), and why the Stack Clash vulnerabilities of 2017 were fixed by widening the gap to 1 MB on Linux.

Secondary threads have no room to grow: their stack is a fixed mmap with a guard page at the bottom, so a thread that recurses overflows sooner than main would — 512 kB on macOS is only ~10,000 small frames — and a thread pool that runs deeply recursive user code is a common place to find this.

C and C++: nothing catches the signal, so the process dies with "Segmentation fault", exit status 139 (128 + 11). The core dump shows tens of thousands of identical frames; gdb prints #0 recurse () … #171303 main (). A deep but finite recursion — a naive recursive descent parser on a long input, a recursive std::variant visit — shows the same symptom without an infinite loop.

JavaScript (V8): the engine checks the stack pointer against a limit on every function entry (an explicit comparison, not the guard page) and throws RangeError: Maximum call stack size exceeded as a catchable exception well before the OS limit — roughly 10,000–15,000 frames in Node with the default ~1 MB V8 stack, fewer with larger frames. node --stack-size=… raises the engine limit but not the thread’s real stack, so setting it too high converts the clean exception back into a segfault.

Python (CPython): the interpreter counts Python-level frames and raises RecursionError: maximum recursion depth exceeded at sys.getrecursionlimit(), 1,000 by default — a soft limit chosen to stay far inside the C stack, because before 3.11 every Python call was also a C-level recursion in the evaluator. Since 3.11 pure-Python calls no longer consume C stack, and 3.12 added a separate C-recursion limit; sys.setrecursionlimit(10**6) still lets you hit the real stack and get a genuine SIGSEGV if C extensions or the evaluator recurse underneath.

Every recursive algorithm you wrote in Recursion & Backtracking, Depth-First Search (DFS) or Divide and Conquer carries a depth bound: linear in the input for a list traversal, the tree height for a tree walk, the recursion depth of quick-sort on adversarial input. A DFS on a 100,000-node path graph is 100,000 frames deep — fine in Go, fatal in Python at the default limit, borderline in Node, and a crash on a 512 kB macOS worker thread in C++. "Works on the test cases" and "overflows in production on a long chain" is one of the most common ways recursive code fails.

The fix is mechanical: a recursion is a loop with an explicit Stack of pending work. What the hardware stack held implicitly — the arguments and the point to resume — becomes a struct you push and pop yourself, on the heap, whose size is limited by memory rather than by a 1 MB region. DFS, tree traversals, flood fill and backtracking all convert this way; memoised recursion converts to Tabulation (Bottom-Up DP) by computing subproblems in dependency order. The trade is readability for a hard depth guarantee, and the conversion is worth doing whenever the depth depends on input you do not control.