C tail call optimization

C tail call optimization (TCO) is a compiler optimization where a function's final call becomes a jump, reusing the same stack frame. Recursive functions calling themselves at the end convert from O(n) stack space to O(1). Optimizers enable TCO with -O2 or higher; not guaranteed.

Write tail-recursive functions to potentially benefit from TCO; don't depend on it for correctness.

// compile: gcc -O2 -o tail_call tail_call.c
// run: ./tail_call
// description: tail call optimization for recursion
 
#include <stdio.h>
 
// Tail-recursive factorial (compiler may optimize)
long factorial_tail(int n, long acc) {
    if (n <= 1)
        return acc;
    return factorial_tail(n - 1, acc * n);  // Tail call
}
 
// Non-tail-recursive factorial (can't optimize)
long factorial_normal(int n) {
    if (n <= 1)
        return 1;
    return n * factorial_normal(n - 1);  // Not tail call
}
 
// Tail-recursive sum
long sum_tail(int n, long acc) {
    if (n <= 0)
        return acc;
    return sum_tail(n - 1, acc + n);  // Tail call
}
 
// Fibonacci tail-recursive (accumulator pattern)
long fib_tail(int n, long a, long b) {
    if (n == 0) return a;
    if (n == 1) return b;
    return fib_tail(n - 1, b, a + b);  // Tail call
}
 
int main() {
    printf("Factorial(10) = %ld\n", factorial_tail(10, 1));
    printf("Sum(100) = %ld\n", sum_tail(100, 0));
    printf("Fib(20) = %ld\n", fib_tail(20, 0, 1));
 
    printf("Large factorial(1000) = %ld\n", factorial_tail(1000, 1));
 
    return 0;
}

Tail call definition:

• Function's last operation is a call
• Return value is the call's return
• No computation after the call

Compiler requirements:

• Not guaranteed (depends on compiler, optimization level)
• GCC/Clang: -O2 or higher usually enables
• MSVC: /O2 or higher
• Embedded/debug builds may not optimize

Accumulator pattern:

• Pass intermediate result as parameter
• Converts non-tail recursion to tail
• Example: factorial_tail(n-1, acc*n) vs n * factorial(n-1)

Benefits:

• O(1) stack space instead of O(n)
• Can recurse deeply without stack overflow
• No speed penalty (jump replaces call)

When TCO matters:

• Very deep recursion (thousands+)
• Real-time code with limited stack
• Most normal code: TCO is bonus, not requirement

Limitations:

• Not guaranteed by C standard
• Function signature must allow accumulator
• Some languages guarantee TCO (Scheme); C doesn't

Debugging note:

• With TCO: stack trace shows one frame (optimized away)
• Without TCO: stack shows full chain
• Can make debugging harder

Alternatives:

• Convert to loop (portable, clear)
• Use explicit stack (if recursion needed)
• Don't over-optimize without profiling