8.10 Recursion and Tail Call Optimization

A function is recursive when it calls itself. Recursion is useful for problems that can be broken down into smaller subproblems of the same type, such as factorials, tree traversals, or certain mathematical sequences.

In most programming languages, including Rust, function calls store local variables, return addresses, and other state on the call stack. Because the stack has limited space, deep recursion can cause a stack overflow. Moreover, maintaining stack frames may make recursion slower than iteration in performance-critical areas.

8.10.1 Recursive Functions

Rust allows recursive functions just like C:

fn factorial(n: u64) -> u64 {
    if n == 0 {
        1
    } else {
        n * factorial(n - 1)
    }
}

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

Each recursive call creates a new stack frame. For factorial(5), the calls unfold as:

factorial(5) → 5 * factorial(4)
factorial(4) → 4 * factorial(3)
factorial(3) → 3 * factorial(2)
factorial(2) → 2 * factorial(1)
factorial(1) → 1 * factorial(0)
factorial(0) → 1

When unwinding these calls, the results multiply in reverse order.

8.10.2 Tail Call Optimization

Tail call optimization (TCO) is a technique where, for functions that make a self-call as their final operation, the compiler reuses the current stack frame instead of creating a new one.

A function is tail-recursive if its recursive call is the last operation before returning:

fn factorial_tail(n: u64, acc: u64) -> u64 {
    if n == 0 {
        acc
    } else {
        factorial_tail(n - 1, n * acc) // Tail call
    }
}

Benefits of Tail Call Optimization

  • Prevents stack overflow: It reuses the current stack frame.
  • Improves performance: Less overhead from stack management.
  • Facilitates deep recursion: Particularly in functional languages that rely on TCO.

Does Rust Support Tail Call Optimization?

Rust does not guarantee tail call optimization. While LLVM might apply it in certain cases, there is no assurance from the language. Consequently, deep recursion in Rust can still lead to stack overflows, even if the function is tail-recursive.

To avoid stack overflows in Rust:

  • Use an iterative approach when feasible.
  • Use explicit data structures (e.g., Vec or VecDeque) to simulate recursion without deep call stacks.
  • Manually rewrite recursion as iteration if necessary.