Recursive Functions

A recursive function is a function that calls itself—either directly (f calls f) or indirectly (f calls g, which calls f)—to solve a problem by breaking it down into smaller subproblems of the same shape.

Essential Anatomy of a Recursive Function

Every terminating recursive function requires two components:

1. Base case: One or more stopping conditions that produce an answer directly without making another recursive call.
2. Recursive step: One or more calls to the function itself with arguments that move strictly closer to the base case.

factorial(4)
  └── 4 * factorial(3)              (Recursive step: n -> n - 1)
            └── 3 * factorial(2)    (Recursive step: n -> n - 1)
                      └── 2 * factorial(1)
                                └── 1   <-- Base case (n <= 1): stops recursion!
                      └── 2 * 1 = 2
            └── 3 * 2 = 6
  └── 4 * 6 = 24

fn factorial(n: u64) -> u64 {
    if n <= 1 {
        1 // Base case: stops recursion
    } else {
        n * factorial(n - 1) // Recursive step: shrinks `n` toward `1`
    }
}

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

0! = 1
5! = 120

Unwinding vs Winding Phases of Execution

Statements placed before the recursive call execute on the way down (the winding phase, as stack frames are pushed), while operations placed after the recursive call execute in reverse order on the way back up (the unwinding phase, as stack frames return):

fn trace_depth(level: u32) {
    if level == 0 {
        println!("  [Base case reached at level 0]");
        return;
    }

    println!("Entering level {level} (winding)");
    trace_depth(level - 1);
    println!("Leaving  level {level} (unwinding)");
}

fn main() {
    trace_depth(3);
}

Entering level 3 (winding)
Entering level 2 (winding)
Entering level 1 (winding)
  [Base case reached at level 0]
Leaving  level 1 (unwinding)
Leaving  level 2 (unwinding)
Leaving  level 3 (unwinding)

Recursive Slice Processing (Divide and Conquer)

In Rust, recursion over arrays or vectors is clean and allocation-free when written over slices (&[T]). Using slice pattern matching ([first, rest @ ..]) or midpoint splitting (slice.split_at(mid)) avoids index arithmetic entirely:

fn sum_slice(values: &[i32]) -> i32 {
    match values {
        [] => 0,                                  // Base case: empty slice
        [first, rest @ ..] => first + sum_slice(rest), // Recursive step on remaining sub-slice
    }
}

fn max_divide_and_conquer(values: &[i32]) -> Option<i32> {
    match values {
        [] => None,
        [single] => Some(*single),
        _ => {
            let mid = values.len() / 2;
            let (left, right) = values.split_at(mid);
            let left_max = max_divide_and_conquer(left)?;
            let right_max = max_divide_and_conquer(right)?;
            Some(left_max.max(right_max))
        }
    }
}

fn main() {
    let numbers = [14, 7, 29, 3, 42, 18];
    println!("Sum: {}", sum_slice(&numbers));
    println!("Max: {:?}", max_divide_and_conquer(&numbers));
}

Sum: 113
Max: Some(42)

Notice that max_divide_and_conquer halves the slice length on each step, so its maximum recursion depth is $\lceil \log_2(N) \rceil + 1$ (only ~20 stack frames even for a slice of 1,000,000 elements!).

Tail-Recursive Accumulator Pattern

In n * factorial(n - 1), the multiplication n * ... happens after the recursive call returns, forcing the CPU to keep n alive on the stack across every frame.

In a tail-recursive function, the recursive call is the very last operation performed by the function, and the running result is passed forward in an accumulator parameter:

fn factorial_tail(n: u64) -> u64 {
    fn helper(n: u64, acc: u64) -> u64 {
        if n <= 1 {
            acc
        } else {
            helper(n - 1, acc * n) // Tail call: no work remains after `helper` returns
        }
    }

    helper(n, 1)
}

fn main() {
    println!("factorial_tail(6) = {}", factorial_tail(6));
}

factorial_tail(6) = 720

Important: While LLVM frequently optimizes self-tail-recursive calls like helper(n - 1, acc * n) into a jump loop when optimizations (-O / --release) are enabled, Rust does not guarantee Tail Call Elimination (TCE) in debug builds (opt-level = 0). For linear loops over large $N$, prefer for or while loops so debug builds cannot overflow the call stack.

Mutual Recursion

Because function items in the same scope are order-independent, two or more functions can call each other without forward declarations:

fn collatz_even(n: u64, steps: u32) -> u32 {
    let next = n / 2;
    if next == 1 {
        steps + 1
    } else if next % 2 == 0 {
        collatz_even(next, steps + 1)
    } else {
        collatz_odd(next, steps + 1)
    }
}

fn collatz_odd(n: u64, steps: u32) -> u32 {
    if n == 1 {
        return steps;
    }
    let next = 3 * n + 1; // Always even
    collatz_even(next, steps + 1)
}

fn main() {
    println!("Collatz steps for 6: {}", collatz_even(6, 0));
}

Collatz steps for 6: 8

Unconditional Recursion Warning (unconditional_recursion)

If you write a function that calls itself on every control-flow path with no base case, rustc detects the bug statically and emits the unconditional_recursion warning:

fn broken_countdown(n: u32) -> u32 {
    broken_countdown(n - 1)
}

fn main() {}

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