Recursion and the stack

In Rust a recursive function calls itself on a smaller input. Each call costs a stack frame, so a recursion needs a base case and an argument that moves towards it; when either is missing the program reaches the end of the stack and dies. Rust makes both halves visible: the compiler warns about a function that cannot return, and GDB shows the frames when the stack runs out.

This lesson writes four recursions that terminate and one that does not. The arithmetic is the smallest that shows the shape, so the stack order stays readable in the output.

A base case and a step

factorial(n) is n * factorial(n - 1), and factorial(0) is one. The second line is the base case, the first is the step, and the argument shrinks by one each time. Five factorial is one hundred and twenty.

The multiplication happens on the way back from the deepest call, so every frame has to stay alive until the base case returns. That is why the depth is bounded by the stack even though the arithmetic is tiny.

fn factorial(n: u32) -> u32 { if n <= 1 { return 1; } n * factorial(n - 1) } fn main() { println!("{}", factorial(5)); }

rustc --edition 2024 factorial.rs
./factorial

120

The result is a u32, so a large argument would overflow before the stack does. The debug build panics on that overflow, which the lesson on numbers shows.

The order of calls and returns

A function can print before and after the recursive call. The first line runs on the way down, the code after the call runs when the deeper call returns, so the output shows the descent and then the ascent.

The program counts down to one and prints on the way back. The last call returns first, which is the last-in-first-out order of the stack made visible in six lines.

fn countdown(n: u32) { println!("enter {n}"); if n > 1 { countdown(n - 1); } println!("leave {n}"); } fn main() { countdown(3); }

rustc --edition 2024 unwind.rs
./unwind

enter 3
enter 2
enter 1
leave 1
leave 2
leave 3

The same order explains why a recursive function that allocates a value per frame keeps every allocation alive until the base case returns. An iterative version would release each one as it goes, which the lessons on iterators prefer for long inputs.

Euclid

The greatest common divisor has a recursive definition that shrinks the pair every time: gcd(a, b) is gcd(b, a % b), and gcd(a, 0) is a. Each step replaces the larger number with a remainder, so the number of calls is logarithmic.

The program prints twenty-one for 1071 and 462. The recursion is naturally a recursion here, and the loop version needs a temporary and three assignments.

fn gcd(a: u32, b: u32) -> u32 { if b == 0 { return a; } gcd(b, a % b) } fn main() { println!("{}", gcd(1071, 462)); }

rustc --edition 2024 gcd.rs
./gcd

21

Because the depth is logarithmic, this recursion never comes near the stack limit, even for numbers that would overflow the call stack if the step were linear.

An explicit depth limit

When the depth depends on input from outside, a limit turns a crash into a result. The function below stops at a step count and returns how far it got, so a caller can report that the limit was reached instead of dying.

The first call walks five steps and the second is capped at one hundred. Both return, and the output says which number came from which call.

fn walk(step: u32, limit: u32) -> u32 { if step >= limit { return step; } walk(step + 1, limit) } fn main() { println!("steps: {}", walk(0, 5)); println!("capped: {}", walk(0, 100)); }

rustc --edition 2024 depth.rs
./depth

steps: 5
capped: 100

A recursive parser or a directory walk uses the same shape, because the input may be hostile and the stack is a fixed resource. The lesson on paths and directories walks a tree with an explicit stack.

No base case

The function below adds one to its argument and calls itself with no way out. rustc recognises the shape and warns that the function cannot return without recursing, then compiles it anyway, because a warning is not an error by default.

Running it fills the stack until the process touches the guard page. On this system the process dies with SIGSEGV and no Rust message, and gdb shows the same frame repeated: that repetition is the definition of a stack overflow.

fn dive(n: u32) -> u32 { dive(n + 1) + 1 } fn main() { println!("{}", dive(0)); }

rustc --edition 2024 dive.rs

warning: function cannot return without recursing
--> dive.rs:1:1
|
1 | fn dive(n: u32) -> u32 {
| ^^^^^^^^^^^^^^^^^^^^^^ cannot return without recursing
2 | dive(n + 1) + 1
| ----------- recursive call site
|
= help: a `loop` may express intention better if this is on purpose
= note: `#[warn(unconditional_recursion)]` on by default

warning: 1 warning emitted

GDB catches the signal at the point where the stack ran out. The addresses change on every run and are suppressed here; what stays is the frame number and the repeated function name.

gdb -q -batch -iex 'set auto-load python-scripts off' -ex 'set disable-randomization off' -ex 'set print address off' -ex run -ex 'bt 4' ./dive


Program received signal SIGSEGV, Segmentation fault.
dive::dive ()
#0 dive::dive ()
#1 dive::dive ()
#2 dive::dive ()
#3 dive::dive ()

The fix is a base case, or a loop, which uses one frame instead of thousands. The compiler offers the same advice in the warning: a loop may express the intention better.

Exercises

  1. Write a recursive sum of the digits of a number and test it with 12345 and with 0. Which case is the base case?
  2. Rewrite factorial as a loop and compare the two for n equal to 20. Which one overflows first?
  3. Call the depth function with a limit of one million. What happens on this machine, and how would the limit prevent it?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What is a base case in a recursion?

    Answer

    The input for which the function returns without calling itself

    Without a case that stops the descent the calls never end and the stack runs out.

  2. What does each recursive call cost?

    Answer

    A stack frame for the parameters and the return address

    The frames accumulate until the base case returns, which bounds the depth.

  3. In what order do recursive calls return?

    Answer

    The last call returns first

    The stack is last in, first out, so the deepest call finishes before its caller.

  4. What does rustc say about a function that always calls itself?

    Answer

    It warns that the function cannot return without recursing

    The unconditional_recursion lint warns and still compiles, because a warning is not an error by default.

  5. What does this program print? fn factorial(n: u32) -> u32 { if n <= 1 { return 1; } n * factorial(n - 1) } fn main() { println!("{}", factorial(5)); }

    Answer

    120

    The recursion multiplies five by four, three, two and one before the base case returns.

  6. What does this program print? fn countdown(n: u32) { println!("enter {n}"); if n > 1 { countdown(n - 1); } println!("leave {n}"); } fn main() { countdown(3); }

    Answer

    enter 3 / enter 2 / enter 1 / leave 1 / leave 2 / leave 3

    The calls descend to one, and the prints after the call come back in reverse order.

  7. What does this program print? fn gcd(a: u32, b: u32) -> u32 { if b == 0 { return a; } gcd(b, a % b) } fn main() { println!("{}", gcd(1071, 462)); }

    Answer

    21

    Euclid on 1071 and 462 reaches twenty-one, their greatest common divisor.

  8. What does this program print? fn walk(step: u32, limit: u32) -> u32 { if step >= limit { return step; } walk(step + 1, limit) } fn main() { println!("steps: {}", walk(0, 5)); println!("capped: {}", walk(0, 100)); }

    Answer

    steps: 5 / capped: 100

    The first call stops after five steps and the second at the hundred-step limit.

  9. What does this program print? fn count(n: u32) -> u32 { if n == 0 { return 0; } 1 + count(n - 1) } fn main() { println!("{}", count(4)); }

    Answer

    4

    Each call adds one and the base case returns zero, so four calls add up to four.

  10. What happens when the program with fn dive(n: u32) -> u32 { dive(n + 1) + 1 } is run?

    Answer

    It receives SIGSEGV when the stack is exhausted

    The frames grow until the guard page is touched, and the process dies with SIGSEGV before any Rust code can report it.

The code on this page was built with rustc 1.96.1 and GDB 16.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev