Ivan's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# 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.

## Example

```c
// 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;
}
```

## Common patterns

**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