Tail Call Optimization

When working into low level system, optimization becomes important especially for reduce time and space complexity. One useful technique in this context is Tail Call Optimization (TCO). It allows certain recursive function to executed more efficiently by reusing the current function stack frame instead of create a new one for each call. As a result, tail-recursive functions improving performance in languages or compilers that support TCO.

int recursive(int n, int acc) {
    if (n == 0) return acc; // base case
    return recursive(n - 1, acc * n); // tail call
}

📚 Call stack

A good place to understand this concept, is to look the Call Stack.

Every time a function is called, the program creates a stack frame on the call stack. This frame stores:

• Function parameter
• Any local variable
• Return address, which tells the CPU where to continue execution after the function finishes

When one function calls another, a new stack frame is added to the stack. When the called function returns, the frame is removed, and execution resumes at the saved return address.

Normally, this works well. However, if too many function calls are made without returning, the call stack can grow too large and cause a stack overflow.

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

This is most common with recursive functions, where a function repeatedly calls itself with modified arguments until it reaches a base case that stops the recursion. If the recursion becomes too deep, each call adds another stack frame, eventually exhausting the available stack space.

→ Error: Stack frame limit exceeded
 → factorial(n)
  → ...
   → factorial(3)
    → factorial(2)
     → factorial(1)

TCO helps programmer to reduce the space complexity of stack frame from O(n) to O(1), exact details will depend on hardware architecture and operating system ABI.

↪️ Jump Instruction

Let’s see this optimization image below, I use tools Compiler Explorer for debugging.

if the code is not optimize the function will use call instruction in and add to stack frame and cost more to memory. TCO help this to optimize the assembly code from using call instruction and use jump instruction instead.

To optimize this programmer need use feature of compiler. In gcc you can use option this when build:

$ gcc -O2 -foptimize-sibling-calls

LLVM compiler have directive [[clang::musttail]] for you to explicitly use TCO:

int get_value(int);

int recursive(int n) {
    [[clang::musttail]]
    return get_value(n);
}

🔄 Recursive calls

Tail call optimization also plays a central role in functional programming languages especially Recursive Function will change into loops.

A good compiler transform from this:

factorial(5, 1)
 → factorial(4, 5)
  → factorial(3, 20)
   → ...

into something equivalent to:

int factorial(int n, int acc) {
    while (n != 0) {
        acc *= n;
        n--;
    }
    return acc;
}