Recursion and the size of the stack¶

Level: 201 · working knowledge

One line: Every nested call adds a frame and nothing releases it until that call returns, so depth costs memory out of a region that is fixed when the thread is spawned and cannot grow — and running out of it aborts the process rather than returning an error.

fn sum(n: u64) -> u64 {
    if n == 0 { 0 } else { n + sum(n - 1) }   // one frame per step
}

let total = sum(5_000);        // 5,000 frames alive at the deepest point
println!("{total}");           // 12502500

That works. sum(5_000_000) does not, and the way it fails is the subject of this page: no panic, no Result, no catch_unwind — the process is killed where it stands.

Frames accumulate, and are released in reverse¶

A recursive call is an ordinary call, so everything on the previous page applies: a region is reserved, arguments move in, the region is released on return. What makes recursion different is only that the caller has not returned yet, so its frame is still there when the callee gets its own.

At the bottom of descend(1, 4) there are four frames and four live values. Then they unwind innermost-first. The rest of this page walks the remaining parts of the same run.

The verified output¶

Verified output of recursion_and_the_stack.rs — regenerated by tools/run_examples.py, never hand-typed.

1. Every nested call adds a frame, and nothing leaves until it returns
   entering frame 1
   entering frame 2
   entering frame 3
   entering frame 4
   deepest frame reached; 4 markers are alive at once
       [drop] the marker in frame 4 is released
       [drop] the marker in frame 3 is released
       [drop] the marker in frame 2 is released
       [drop] the marker in frame 1 is released
   ...and they are released in reverse, innermost first

2. Depth is the cost, not the work
   sum_recursive(5000) = 12502500   5000 frames, one per step
   sum_iterative(5000) = 12502500   one frame, whatever n is
   same answer; only one of the two has a depth limit
   sum_iterative(1000000) = 500000500000
   the recursive version cannot be asked that. Part 4 shows what happens.

3. The bound is chosen when a thread is spawned, and never grows
   a thread asked for 256 KiB ran 1,000 frames fine: 500500
   there is no reallocation and no growth: a stack is a fixed region,
   so the only question is whether the depth fits the one you asked for

4. Running out is an abort. Not a panic, not a Result.
   child recursed without a base case, and exited successfully? false
   the runtime named the reason on stderr:                      true
   the same run wrapped in catch_unwind, exited successfully?   false
   and it still died with the same message:                     true
   catch_unwind catches PANICS. An overflow does not unwind, so there
   is nothing to catch -- the process is killed where it stands.

5. What this leaves behind
   a panic runs every Drop on the way out; an abort runs none.
   files stay open, locks stay locked, buffers stay unflushed --
   the OS reclaims the memory, and nothing else gets a say.

The cost is the depth, not the work¶

sum_recursive(5_000) and sum_iterative(5_000) produce the same number. One holds 5,000 frames at its deepest point; the other holds one, whatever n is, because the pending work became a counter in a register instead of a stack of half-finished calls.

That is the whole trade, and it is why "rewrite it as a loop" is the standard fix. Rust does not guarantee tail-call elimination — there is no become on stable, and LLVM may or may not turn a tail-recursive function into a loop depending on the optimization level and the shape of the code. A program that only survives because the optimizer helped is a program that overflows the day someone builds it in debug.

The bound is chosen at spawn and never grows¶

A stack is a fixed region. There is no reallocation, no doubling, no "ask the OS for more" — which is exactly the opposite of how a Vec behaves, and the reason a depth limit exists at all.

Thread	Size	Set by
main	typically 8 MiB on Linux and macOS	the OS, at process start (`ulimit -s`)
spawned, default	2 MiB	Rust's default, overridable with `RUST_MIN_STACK`
spawned, explicit	whatever you ask for	`Builder::stack_size` ↗

Those numbers are conventions rather than language guarantees, which is why the example above prints none of them — it asks for 256 KiB explicitly and shows that a 1,000-frame recursion fits. The useful habit is to stop asking "how deep can I go" (unanswerable: it depends on frame size, build profile, platform and thread) and start asking "is this depth bounded by my data". Recursing over a balanced tree is fine. Recursing over user input is not.

Overflow is an abort, not a panic¶

This is the part worth carrying, and the example proves it by re-running itself and letting the child die.

child recursed without a base case, and exited successfully? false
the runtime named the reason on stderr:                      true
the same run wrapped in catch_unwind, exited successfully?   false

A panic unwinds: it runs every Drop on the way out, and catch_unwind ↗ can stop it at a boundary. A stack overflow does neither. Rust detects it with a guard page, prints thread '…' has overflowed its stack to stderr, and aborts — because there is no stack left to run a destructor on, which is precisely the resource unwinding would need.

So nothing you write catches it, and nothing you registered runs:

	Panic	Stack overflow
`Drop` impls run	yes (with `panic = "unwind"`)	no
`catch_unwind` stops it	yes	no
Recoverable in-process	at a boundary	never
Buffers flushed, locks released	on the way out	not by you — the OS reclaims the memory and nothing else

The consolation is that it is detected. A guard page turns what would be silent corruption in C into a message and an abort, which is a hard failure rather than a wrong answer.

Where this bites in ordinary code¶

Recursive Drop. Dropping a long boxed linked list drops its next, which drops its next — one frame per node, in the destructor, at the end of a scope, with a backtrace that names nothing you wrote. Box has the worked case.
A parser on hostile input. Deeply nested JSON or S-expressions turn input depth into stack depth. serde_json caps recursion for this reason; a hand-rolled descent parser usually does not until someone finds out.
A big array in a frame. let buf = [0u8; 8_000_000]; overflows before a single call is made — an array's elements are the frame, so Box or Vec is the fix.
Debug builds. Frames are larger without optimization, so the depth that works in --release is not the depth that works under cargo test.

If you are coming from another language¶

Python. The counterpart is RecursionError, and the two differences both matter. CPython counts frames, not bytes: the limit is 1,000 (sys.getrecursionlimit()), it is checked in the interpreter loop, and exceeding it raises an ordinary exception you can catch, with finally blocks running normally on the way out. Rust's limit is the real one — bytes of a real stack — so it depends on how big your frames are and cannot be stated as a number of calls, and hitting it is an abort rather than an exception. The Python trap that transfers exactly is sys.setrecursionlimit(100000): raising the counter does not enlarge CPython's C stack, so the program stops raising a catchable error and starts segfaulting instead. That is Rust's failure mode all along, which is why Rust never offered the catchable version.

ABAP. You have met this as short dump TSV_TNEW_PAGE_ALLOC_FAILED or a recursion depth dump from a FORM calling itself; the ABAP kernel bounds the internal session's memory rather than a byte-sized stack, and the roll area is configured by basis parameters (ztta/roll_area, abap/heap_area_dia) instead of by the program. Two things differ. ABAP's dump is catchable in the sense that the work process survives and the user gets ST22 to read; Rust's abort takes the process out, so there is no equivalent of "look at the dump afterwards" beyond a core file. And the ABAP habit of recursing over a hierarchy read from a table — a BOM explosion, an org tree — is exactly the pattern this page says to bound: if the depth comes from the data, an explicit work table (APPEND a to-do row, LOOP until empty) is the version that cannot dump, and it is the same rewrite as Rust's worklist.

C. Identical mechanism, and Rust adds one thing: the guard page is on by default and the message names the cause. In C a stack overflow is a SIGSEGV with no explanation, or — if the frame is big enough to skip past the guard page — silent corruption of whatever was below the stack, which is the classic "stack clash" vulnerability class. C compilers also do perform tail-call elimination at -O2, so recursive C code often survives depths Rust's debug build will not; the C habit of relying on that does not transfer, because Rust promises nothing here at any level.

C++. Same as C, plus one Rust-specific relief: alloca and C99 variable-length arrays have no safe Rust counterpart, so the unbounded frame — a frame whose size comes from a run-time value — cannot be written by accident. In Rust a frame's size is fixed at compile time, so depth is the only thing that varies, which makes the failure mode easier to reason about even though it is less recoverable.

Po polsku¶

Każde zagnieżdżone wywołanie dokłada ramkę i nic jej nie zwalnia, dopóki to wywołanie nie wróci. Kosztem rekurencji jest więc głębokość, a nie ilość pracy: sum_recursive(5000) i sum_iterative(5000) dają ten sam wynik, ale pierwsza wersja trzyma 5 000 ramek naraz, a druga jedną.

Rozmiar stosu jest ustalany przy tworzeniu wątku i nigdy nie rośnie — to nie jest Vec, który się podwaja. Wątek główny dostaje zwykle 8 MiB od systemu, wątek utworzony przez thread::spawn domyślnie 2 MiB, a thread::Builder::new().stack_size(n) pozwala poprosić o konkretną wartość.

Najważniejsza różnica wobec innych języków: przepełnienie stosu to abort, a nie panic. Nie ma odwijania stosu, nie uruchamiają się destruktory (Drop), catch_unwind niczego nie łapie — proces jest zabijany w miejscu. Rust wykrywa to stroną strażniczą (guard page) i wypisuje has overflowed its stack na stderr, co jest i tak lepsze niż ciche SIGSEGV w C, ale nie da się tego obsłużyć w programie.

Praktyczna reguła: nie pytaj „jak głęboko mogę zejść” (odpowiedź zależy od rozmiaru ramki, profilu kompilacji i platformy), tylko „czy głębokość jest ograniczona przez moje dane”. Rekurencja po zrównoważonym drzewie jest w porządku. Rekurencja po danych od użytkownika — nie; wtedy pisze się pętlę z jawną listą zadań na stercie.

Szukaj po polsku: przepełnienie stosu · rekurencja a stos · rozmiar stosu wątku · optymalizacja wywołań ogonowych · rust stack overflow · stack_size