🎓 A1Learner
🔍

Rust Recursion

Recursion is a technique where a function calls itself. Each call works on a smaller copy of the same problem.

A function that calls itself

count_down prints its number, then calls itself with one less:

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

The base case stops the calls

fact has two cases. The base case, n == 0, answers 1 at once with no new call. The recursive case calls fact on a smaller number and multiplies:

fn fact(n: u32) -> u32 {
    if n == 0 { 1 } else { n * fact(n - 1) }
}
println!("fact(4) = {}", fact(4));

Every call keeps its own n

trace(2) cannot finish until trace(1) answers, and that one waits for trace(0). Each waiting call holds its own n — they never clash:

fn trace(n: u32) -> u32 {
    println!("call with n = {n}");
    if n == 0 { 0 } else { n + trace(n - 1) }
}
println!("total = {}", trace(2));

Example

fn fib(n: u32) -> u32 {
    if n < 2 {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
}
fn main() {
    for n in 0..=10 {
        print!("{} ", fib(n));
    }
    println!();
    println!("fib(20) = {}", fib(20));
}

Key points

  • Waiting calls pile up on the call stack.
  • It is the same stack from Rust Stack & Heap.
  • Each unfinished call waits while the smaller call works.
  • A missing or unreachable base case never stops.
  • The calls pile up until the stack runs out.
  • Then the program crashes — a stack overflow.
  • Use a loop instead when the steps are plain counting: recursion shines when the problem itself splits into smaller copies

In this example, fib works out the Fibonacci sequence, where each number is the sum of the two before it. If n is less than 2, fib gives n back at once — that is the base case, the stop. Otherwise it calls itself twice, on n - 1 and n - 2, and adds the two answers. main prints fib for 0 to 10. The famous sequence appears: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Then it prints fib(20) = 6765. Notice the hidden cost: fib(20) needs fib(19) and fib(18), and each of those calls two more — the calls multiply fast. This pretty version is a teaching tool, not the fastest way.

Note

Some languages promise to tidy up certain self-calls so they take no extra stack room.

Rust makes no such promise: every call takes its space, so very deep recursion can overflow even when written neatly.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

What does the base case of a recursive function do?