7.7Introduction to recursion

Last updated June 12, 2026

A function in Rust may call any function it can see, including, it turns out, itself. A function that calls itself is called recursive, and recursion is this chapter's last way to make code run repeatedly, the only one that needs no loop statement at all.

fn countdown(n: u32) {
    println!("{n}");
    if n > 0 {
        countdown(n - 1);
    }
}

fn main() {
    countdown(3);
}

3
2
1
0

Walk it through. main calls countdown(3), which prints 3 and calls countdown(2), which prints 2 and calls countdown(1)... down to countdown(0), which prints 0 and, with 0 > 0 false, doesn't call again. Then the calls finish in reverse order, each one returning to the countdown that called it, and finally to main.

Two parts make this work, and every correct recursive function has both. The recursive case is the branch that calls the function again, with an argument moved toward the finish (n - 1 here). The base case is the input for which the function doesn't call itself (n == 0 here), which is what ends the chain. A loop's condition and a base case are the same idea wearing different clothes: both answer "when do we stop?"

When you forget the base case

A loop without an exit runs forever. A recursive function without a base case does something more dramatic. Here's one, distilled:

fn deeper(depth: u64) -> u64 {
    deeper(depth + 1)
}

fn main() {
    println!("{}", deeper(1));
}

The compiler sees the problem at compile time and says so:

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

Run it anyway and:

thread 'main' (2296939) has overflowed its stack
fatal runtime error: stack overflow, aborting

Here's why the failure mode is a crash rather than a hang. Every function call claims a small ledge of memory for its local variables and bookkeeping, and that ledge is only released when the call returns. A million unfinished calls means a million ledges, all held at once. The region they're carved from (called the stack) is a few megabytes, and when it's exhausted, the program is over. This is a stack overflow, and yes, the famous website is named after it. The full story of the stack, with diagrams, is lesson 8.2; for this lesson, "each unfinished call holds memory until it returns" is the load-bearing fact.

Note the limits of the compile-time warning: it fires only when no path avoids the recursive call. A function with a base case that's merely unreachable (wrong condition, wrong direction of travel) compiles in silence and overflows at runtime. The compiler checks that a base case exists, not that you'll ever get there; getting there is your half of the contract.

Recursion or a loop?

Lesson 7.5's quiz built sum_to with a for loop. Here it is recursively, side by side:

fn sum_to_loop(value: u32) -> u32 {
    let mut sum = 0;
    for i in 1..=value {
        sum += i;
    }
    sum
}

fn sum_to_recursive(value: u32) -> u32 {
    if value == 0 {
        return 0;   // base case
    }
    value + sum_to_recursive(value - 1)   // recursive case
}

fn main() {
    println!("{}", sum_to_loop(100));
    println!("{}", sum_to_recursive(100));
}

5050
5050

Read the recursive one as a sentence: the sum to 100 is "100 plus the sum to 99," and the sum to 0 is 0. No mutable state, no counter; the definition is the computation. Anything a loop can do, recursion can do, and vice versa, so the choice between them is about clarity and cost.

For sum_to, the loop wins on both counts (the recursive version holds 100 unfinished calls to compute what a single accumulator could). Recursion wins when the problem itself is shaped like smaller copies of itself. The textbook specimen is the Fibonacci sequence, where each number is the sum of the previous two:

fn fibonacci(n: u64) -> u64 {
    if n <= 1 {
        return n;   // base cases: fibonacci(0) = 0, fibonacci(1) = 1
    }
    fibonacci(n - 1) + fibonacci(n - 2)
}

fn main() {
    for n in 0..10 {
        print!("{} ", fibonacci(n));
    }
    println!();
}

0 1 1 2 3 5 8 13 21 34 

The function is nearly a transcription of the mathematical definition, which is recursion's great charm. (It's also spectacularly wasteful here: fibonacci(40) recomputes fibonacci(2) tens of millions of times. A loop version is thousands of times faster. Chapter 19's tools make the fast version pretty, too; until then, enjoy this one as a readable specimen rather than a shippable one.) Recursion's real home turf, structures that branch like trees, arrives with the data types of later chapters.

Quiz time

Question #1

This is countdown with the print moved below the recursive call. What does count(3) print?

fn count(n: u32) {
    if n > 0 {
        count(n - 1);
    }
    println!("{n}");
}

fn main() {
    count(3);
}

0
1
2
3

Question #2

Write a recursive function factorial(n: u64) -> u64 returning n! (the product of 1 through n), where factorial(0) is defined as 1. factorial(5) should return 120.

fn factorial(n: u64) -> u64 {
    if n == 0 {
        return 1;   // base case
    }
    n * factorial(n - 1)
}

fn main() {
    println!("{}", factorial(5));
    println!("{}", factorial(10));
}

120
3628800

Question #3

One of these two programs prints done; the other dies with a stack overflow. Which is which, and why?

// Program A
fn shrink(n: i32) {
    if n == 0 {
        return;
    }
    shrink(n - 2);
}

fn main() {
    shrink(8);
    println!("done");
}

// Program B
fn shrink(n: i32) {
    if n == 0 {
        return;
    }
    shrink(n - 2);
}

fn main() {
    shrink(7);
    println!("done");
}

Next: stopping. Not the loop, the whole program, and the polite and impolite ways to do it.