Rust for C-Programmers

8.10 Recursion and Tail Call Optimization

A function is recursive if it calls itself, either directly or indirectly. Recursion is a natural way to solve problems that can be broken down into smaller, self-similar subproblems.

8.10.1 Recursive Function Example: Factorial

The factorial function is a classic example: n! = n * (n-1)! with 0! = 1.

fn factorial(n: u64) -> u64 {
    if n == 0 {
        1 // Base case
    } else {
        n * factorial(n - 1) // Recursive step
    }
}

fn main() {
    println!("5! = {}", factorial(5)); // Output: 5! = 120
}

Each recursive call adds a new frame to the program’s call stack to store local variables, parameters, and the return address. If the recursion goes too deep (e.g., calculating factorial(100000)), it can exhaust the available stack space, leading to a stack overflow error and program crash. Recursive calls also typically incur some performance overhead compared to iterative solutions.

8.10.2 Tail Recursion and Tail Call Optimization (TCO)

A recursive call is in tail position if it is the very last action performed by the function before it returns. A function where all recursive calls are in tail position is called tail-recursive.

Example: Tail-Recursive Factorial We can rewrite factorial using an accumulator parameter to make the recursive call the last operation:

fn factorial_tailrec(n: u64, accumulator: u64) -> u64 {
    if n == 0 {
        accumulator // Base case: return the accumulated result
    } else {
        // The recursive call is the last thing done.
        factorial_tailrec(n - 1, n * accumulator)
    }
}

// Helper function to provide the initial accumulator value
fn factorial_optimized(n: u64) -> u64 {
    factorial_tailrec(n, 1) // Start with accumulator = 1
}

fn main() {
    println!("Optimized 5! = {}", factorial_optimized(5)); // Output: Optimized 5! = 120
}

Tail Call Optimization (TCO) is a compiler optimization where a tail call (especially a tail-recursive call) can be transformed into a simple jump, reusing the current stack frame instead of creating a new one. This effectively turns tail recursion into iteration, preventing stack overflow and improving performance.

Status of TCO in Rust: Critically, Rust does not currently guarantee Tail Call Optimization. While the underlying LLVM compiler backend can perform TCO in some specific situations (especially in release builds with optimizations enabled), it is not a guaranteed language feature you can rely on.

Implications: Deep recursion, even if written in a tail-recursive style, can still lead to stack overflows in Rust. For algorithms requiring deep recursion or unbounded recursion depth, you should prefer an iterative approach or simulate recursion using heap-allocated data structures (like a Vec acting as an explicit stack) if stack overflow is a concern.