8.10 Tail Call Optimization and Recursion

8.10.1 Recursive Functions

Rust supports recursive functions, similar to C.

fn factorial(n: u64) -> u64 {
    if n == 0 {
        1
    } else {
        n * factorial(n - 1)
    }
}
fn main() {
    let result = factorial(5);
    println!("Factorial of 5 is {}", result);
}

8.10.2 Tail Call Optimization

Tail call optimization (TCO) is a technique where the compiler can optimize recursive function calls that are in tail position (the last action in the function) to reuse the current function's stack frame, preventing additional stack growth.

  • In Rust: Tail call optimization is not guaranteed by the compiler. Deep recursion may lead to stack overflows.
  • Recommendation: For large recursive computations, consider using iterative approaches or explicit stack structures.

Example of Tail Recursion:

fn factorial_tail(n: u64, acc: u64) -> u64 {
    if n == 0 {
        acc
    } else {
        factorial_tail(n - 1, n * acc)
    }
}
fn main() {
    let result = factorial_tail(5, 1);
    println!("Factorial of 5 is {}", result);
}
  • Even though factorial_tail is tail-recursive, Rust does not optimize it to prevent stack growth.