Recursion Optimization

Recursion Optimization in C++: Tail Call Optimization (TCO)

---

Prerequisites

---

1. Why Recursion Can Be Expensive

Recursive functions use the call stack.

• Pushes stack frame
• Stores local variables
• Adds overhead

❌ Deep recursion → stack overflow + performance cost

2. Tail Call Optimization

A recursion where the last operation is a function call

Compiler can optimize:

• Reuse current stack frame
• Avoid additional stack growth

For TCO to work, the recursive call must be the final operation

Non-Tail Recursion (❌ Not Optimized)

int sum(int n) 
{
    if (n == 0) 
        return 0;

    return n + sum(n - 1);
}

• + n happens after recursive call
• Requires stack frame → no TCO

Tail Recursion (✔ Optimizable)

int sum_helper(int n, int acc) 
{
    if (n == 0) 
        return acc;
    
    return sum_helper(n - 1, acc + n);
}

Recursive call is the last operation

2-1. Why +, -, * Break Optimization

return sum(n - 1) + n;  // ❌ breaks TCO

Compiler must:

• Wait for recursive result
• Then perform addition

❌ Cannot reuse stack frame

✔ Typical requirements

• No extra operations after call
• No need for current stack frame

2-2. Another example

❌ Bad (no TCO)

int fact(int n) 
{
    if (n <= 1) 
        return 1;
    
    return n * fact(n - 1);
}

✔ Good (TCO possible)

int fact_helper(int n, int acc) 
{
    if (n <= 1) 
        return acc;
    
    return fact_helper(n - 1, acc * n);
}

Even better:

int sum(int n) 
{
    int acc = 0;

    while (n > 0) 
        acc += n--;

    return acc;
}

✔ No recursion
✔ No stack overhead

✔ DO

• Ensure recursive call is last
• Move operations into parameters (accumulator)
• Use compiler optimization flags

❌ DON’T

• Add operations after recursive call
• Assume TCO always works
• Ignore stack usage