Tail Recursion

Tail recursion is a special form of recursion where the recursive call is the last operation performed by the function. This means there is no pending work after the recursive call returns.

Tail-recursive functions are important because they can be optimized to run like loops in some languages and help reduce stack usage.

What Makes a Function Tail Recursive?

A function is tail recursive if:

• The recursive call is the final statement
• The function returns directly from the recursive call
• No computation is done after the call returns

Not Tail Recursive

fn factorial(n: u64) -> u64 {
    if n == 0 {
        1
    } else {
        n * factorial(n - 1) // work after recursive call
    }
}

Tail Recursive

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

The accumulator (acc) carries the result forward.

Tail Recursion vs Regular Recursion

Why Tail Recursion Matters

Tail recursion:

• Makes recursive logic more efficient
• Simplifies conversion to iteration
• Reduces mental overhead when reasoning about the call stack
• Is a stepping stone to understanding compilers and optimization

Tail Recursion in Rust

⚠️ Important note: Rust does not guarantee tail call optimization (TCO).

This means:

• Tail-recursive functions may still consume stack space
• Large recursion depths can still cause stack overflow

Therefore, iterative solutions are often preferred in Rust.

Example: Tail Recursive Factorial

pub fn factorial(n: u64) -> u64 {
    factorial_helper(n, 1)
}

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

Equivalent Iterative Version

Tail-recursive functions often translate directly to loops.

pub fn factorial_iter(mut n: u64) -> u64 {
    let mut acc = 1;

    while n > 0 {
        acc *= n;
        n -= 1;
    }

    acc
}

This version is:

• Faster
• Stack-safe
• Idiomatic in Rust

Tail Recursion and Backtracking

Backtracking algorithms are not tail recursive because they:

• Explore multiple branches
• Perform work after recursive calls
• Require state rollback

Understanding tail recursion helps clarify why backtracking needs recursion.

Common Mistakes

• Assuming Rust optimizes tail calls
• Forgetting to use an accumulator
• Using recursion when iteration is clearer

Summary

• Tail recursion means recursive call is the last operation
• Allows accumulator-based design
• Can be transformed into loops
• Rust does not guarantee TCO
• Iteration is often preferred in Rust