🎓 A1Learner
🔍

Rust Stack Frames & Recursion

A stack frame is the stack space one function call rents for its locals. Frames pile up as calls nest, one on top of another.

One call, one frame

The + 1 waits for the deeper answer. No frame can close until the deepest one returns:

fn dive(n: u64) -> u64 {
    if n == 0 { 0 } else { dive(n - 1) + 1 }
}

Slim frames go deep

This frame holds almost nothing. On the machine that tested this lesson, a hundred thousand slim frames fit inside the default stack:

println!("slim frames: reached {}", dive(100_000));

Fat frames run out fast

Give each frame a 4 KB buffer of its own and the same stack holds far fewer frames. In the test run, 2,000 calls fit. 5,000 calls overflowed:

fn fat(n: u64) -> u64 {
    let mut buf = [0u8; 4096];
    buf[0] = 7;
    buf[4095] = n as u8;
    std::hint::black_box(&buf);
    if n == 0 { 0 } else { fat(n - 1) + 1 }
}

The overflow message

There is no panic to catch here. The runtime prints two lines and aborts the programme:

// thread 'main' has overflowed its stack
// fatal runtime error: stack overflow, aborting

Rent a bigger stack

A worker thread can be given a much larger stack at birth. The fat dive that overflowed the main stack now finishes:

let handle = std::thread::Builder::new()
    .stack_size(64 * 1024 * 1024)
    .spawn(|| fat(10_000))
    .unwrap();
println!("fat frames in a big stack: reached {}", handle.join().unwrap());

A loop rents one frame only

The same counting job, written as a loop, never rents a second frame:

let mut count = 0u64;
for _ in 0..1_000_000 { count += 1; }
println!("one loop frame: counted {count}");

Example

use std::hint::black_box;

fn slim(n: u64) -> u64 {
    if n == 0 { 0 } else { slim(n - 1) + 1 }
}

fn fat(n: u64) -> u64 {
    let mut buf = [0u8; 4096];
    buf[0] = 7;
    buf[4095] = n as u8;
    black_box(&buf);
    if n == 0 { 0 } else { fat(n - 1) + 1 }
}

fn main() {
    println!("slim frames: reached {}", slim(100_000));
    let handle = std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024)
        .spawn(|| fat(10_000))
        .unwrap();
    println!("fat frames in a big stack: reached {}", handle.join().unwrap());
    let mut count = 0u64;
    for _ in 0..1_000_000 { count += 1; }
    println!("one loop frame: counted {count}");
}

Key points

  • Frame: the stack space one call rents for its locals
  • The space is freed the moment the call returns
  • Rust never promises tail-call optimisation: a self-call in last position still rents a fresh frame
  • An overflow is an abort, not an error: no catch, no Result, the programme stops
  • Use a loop when the depth has no natural limit: a loop rents one frame for the whole job
  • Use std::thread::Builder::stack_size when the recursive shape is right and only the budget is wrong

In this example, one stack is spent three ways. The slim dive rents a tiny frame per call, so a hundred thousand calls fit in the default stack. The fat dive gives every frame a 4 KB buffer. Ten thousand of those frames need about 40 MB. So the work moves to a thread born with a 64 MB stack. It finishes there. The loop at the end counts to a million inside a single frame. Same machine, same stack rules. Only the rent per call changed.

Note

Frame sizes change with build settings

A depth that fits while you develop may fail in the build you ship

Measure the real build

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

A recursive parser aborts on very deep input. The recursive shape fits the problem well. Which fix keeps the shape?