Last updated：2026-10-12

C++ Tail Recursion¶

Tail-call optimization is a special optimization technique applicable to recursive functions that can greatly reduce the stack space consumed by recursive calls. With tail-call optimization, the compiler can avoid creating a new stack frame when executing tail recursion and instead reuse the current stack frame, reducing the risk of stack overflow and improving performance.

What Is Tail Recursion?¶

When a recursive call returns and no other operations remain to be performed, the recursion is called tail recursion. In this situation, the compiler can replace the recursion with a loop structure, avoiding the overhead of repeated function calls.

An Example of Non-Tail Recursion (Fibonacci)¶

Your fibonacci_non_tail() function is a standard non-tail-recursive implementation:

int fibonacci_non_tail(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci_non_tail(n - 1) + fibonacci_non_tail(n - 2);
}

In this implementation, after the recursive calls fibonacci_non_tail(n - 1) and fibonacci_non_tail(n - 2) return, their results still have to be added together, so this is not tail recursion. Every call must save context information so that computation can resume after the recursion returns, causing the stack space to grow rapidly.

Example of Tail-Call Optimization¶

fibonacci_tail() takes the tail-recursive approach:

int fibonacci_tail_helper(int n, int a, int b) {
    if (n == 0) {
        return a;
    }
    return fibonacci_tail_helper(n - 1, b, a + b);
}

int fibonacci_tail(int n) {
    return fibonacci_tail_helper(n, 0, 1);
}

Here fibonacci_tail_helper() is tail recursive. As you can see, after the recursive call fibonacci_tail_helper(n - 1, b, a + b), the function has nothing left to do: it directly returns the result of the recursive call. The recursive call is therefore in the "tail" of the function, with no additional operations to perform after it.

Advantages of Tail-Call Optimization¶

Less stack space usage: since the context of recursive calls does not need to be saved, the compiler can reuse stack frames and avoid stack bloat.
Prevents stack overflow: tail-call optimization allows the recursion depth to reach very large values without a stack overflow.
More efficient: on compilers that support tail-call optimization, tail recursion performs close to an iterative implementation, eliminating the overhead of recursive function calls.

Performance Testing¶

Finally, a benchmark of the above shows that tail-call optimization is very useful in this scenario — you can see the performance difference is huge!