Stack Frames and Recursion

Every time a function is called in Rust—whether it calls a different function or calls itself recursively—the CPU allocates a stack frame (also called an activation record) on the thread's call stack to hold that specific invocation's parameters, local variables, and return address.

What Lives Inside a Stack Frame

Each active function call owns its own isolated stack frame. When function A calls function B, B's stack frame is pushed directly on top of A's frame; when B returns, its frame is popped in $O(1)$ time by adjusting the CPU's stack pointer register (sp / rsp):

High Memory Addresses
+---------------------------------------+
| Stack Frame: main()                   |
|   - Local variable: n = 3             |
|   - Return address (OS entry)         |
+---------------------------------------+  <-- main() calls sum_to(3)
| Stack Frame: sum_to(n = 3)            |
|   - Parameter: n = 3                  |
|   - Return address (inside main)      |
+---------------------------------------+  <-- sum_to(3) calls sum_to(2)
| Stack Frame: sum_to(n = 2)            |
|   - Parameter: n = 2                  |
|   - Return address (inside sum_to(3)) |
+---------------------------------------+  <-- sum_to(2) calls sum_to(1)
| Stack Frame: sum_to(n = 1) [Base Case]|
|   - Parameter: n = 1                  |
|   - Return address (inside sum_to(2)) |
+---------------------------------------+  <-- CPU Stack Pointer (SP) at peak depth
Low Memory Addresses (Stack grows downward on x86_64 and ARM64)

Observing Distinct Stack Frame Addresses in Recursion

In a recursive function fn sum_to(n: u32), the parameter n is not a single shared variable across calls. Each recursive invocation allocates a brand-new n at a different memory address inside its own stack frame:

fn sum_to(n: u32) -> u32 {
    println!("  depth n = {n}: address of `n` on stack = {:p}", &n);

    if n <= 1 {
        1
    } else {
        n + sum_to(n - 1)
    }
}

fn main() {
    let total = sum_to(4);
    println!("Total = {total}");
}

  depth n = 4: address of `n` on stack = 0x16fdff1dc
  depth n = 3: address of `n` on stack = 0x16fdff18c
  depth n = 2: address of `n` on stack = 0x16fdff13c
  depth n = 1: address of `n` on stack = 0x16fdff0ec
Total = 10

Notice how the memory address of &n decreases by a fixed number of bytes (0x50 = 80 bytes in an unoptimized debug build) on each recursive call as the stack grows downward, and all four instances of n (4, 3, 2, 1) exist simultaneously on the stack until the base case n == 1 returns!

Stack Space Complexity ($O(D)$ vs $O(1)$)

Because each active recursive call holds a stack frame until it returns, the memory consumed by a recursive algorithm is proportional to its maximum recursion depth $D$ multiplied by the size of each stack frame:

Algorithm Pattern	Example	Max Stack Frames Active Simultaneously	Stack Memory Complexity
Iterative loop (for / while)	Summing 1..=N in a loop	1 (reuses the same local variables)	$O(1)$ constant stack space
Linear recursion	sum_to(N) calling sum_to(N - 1)	N frames deep	$O(N)$ linear stack space
Balanced binary recursion	Binary search or merge sort on N items	$\approx \log_2(N)$ frames deep	$O(\log N)$ logarithmic stack space

Why Tree Recursion Uses Only $O(\text{height})$ Stack Space

Even if a recursive function makes two recursive calls per step (such as traversing a binary tree or computing Fibonacci numbers fib(n - 1) + fib(n - 2)), the two calls do not execute at the same time!

1. First, the left call fib(n - 1) runs to completion and pops all of its stack frames.
2. Second, the right call fib(n - 2) reuses the exact same stack memory that was just freed by the left call.

Stack Reuse During `fib(3)` -> calls `fib(2)` then `fib(1)`:
  Step 1: [fib(3)] -> [fib(2)] -> [fib(1)]   (Peak depth = 3 frames)
  Step 2: [fib(3)] -> [fib(2)]               (`fib(1)` returned and popped!)
  Step 3: [fib(3)]                           (`fib(2)` returned and popped!)
  Step 4: [fib(3)] -> [fib(1)]               (Second branch reuses freed stack space!)

Therefore, even when total recursive calls are $O(2^N)$, the stack memory used at any instant is bounded by the longest path from root to base case ($O(N)$ depth).

Minimizing Stack Frame Size in Recursive Functions

If a recursive function declares large stack arrays inside its body (for example, let buffer = [0_u8; 65536];), every single recursive step adds 64 KB to the call stack, exhausting a 2 MB thread stack in just 30 calls!

To keep recursive stack frames small:

• Pass slices (&[T] or &mut [T], which are only 16 bytes) instead of passing large fixed-size arrays ([T; 1024]) by value.
• Allocate large temporary buffers on the heap (Vec<T> or Box<[T]>) or move them outside the recursive function and pass a mutable reference &mut Buffer down the recursion tree:

fn traverse_with_shared_scratch(depth: usize, scratch: &mut Vec<u32>) -> u32 {
    if depth == 0 {
        return scratch.iter().sum();
    }

    // Reuse the single caller-provided `Vec` instead of allocating a new buffer per frame:
    scratch.push(depth as u32);
    let result = traverse_with_shared_scratch(depth - 1, scratch);
    scratch.pop(); // Restore state on unwind
    result
}

fn main() {
    let mut shared_buffer = Vec::with_capacity(10);
    let sum = traverse_with_shared_scratch(5, &mut shared_buffer);
    println!("Sum = {sum}, scratch len after return = {}", shared_buffer.len());
}

Sum = 15, scratch len after return = 0