Basics of Tail Call Optimization

What is Tail Call Optimization?

Tail call optimization is an optimization technique which eliminates the risk of stack overflow which occurs when there are too many function calls. This technique is used for tail recursive functions by reusing the same activation record (or stack frame) of a function call. In this way, there is no chance of stack overflow as there is only one stack frame in the stack for multiple function calls.

What is a Tail Call?

To properly understand tail call optimization, we need to understand the meaning of tail call. So, what is a tail call? Tail call occurs when a function calls another function as the last operation. There must not be another operation after the function is called, however, value obtained as the result after the function call can be returned.

For example, the following function is an example of tail call:

int tailCallFunction(int n) {
    return anotherFunction(n);
}

Understanding Tail Recursion

Tail recursion occurs when a recursive function calls itself as the last operation. 

For example, the following factorial function is a Tail recursive function as there is no operation after the recursive call except returning the result:

#include <stdio.h>

int fact(int n, int result) 
{
     if (n == 1) 
         return result;
     else 
         return fact(n-1, n * result);    
}

int main() {
    printf("Factorial: %d", fact(5, 1));
}

Focus on the fact() function. All the Operations required to perform factorial of a number is done within the function calls. Hence, calling a function is the last operation.

How Tail Call Optimization Works?

Normally, when a function is called, a new stack frame (or activation record) is created and pushed inside the call stack. The stack frame of a function contains information such as the return address, local variables, and so on. For a deeply recursive function, many stack frames can be created leading to stack overflow which means the stack is full and there is no space left for another stack frame.

When the compiler sees that the recursive function is tail recursive, it can choose to reuse the stack frame for multiple function calls. This technique is called Tail Call Optimization which is possible for tail recursive functions. In this way, only one stack frame is needed for multiple function calls significantly reducing the memory usage and chances of stack overflow.

Remember multiple stack frames are useful when operations need values exclusively from the function calls. Consider the following factorial function where the need of multiple stack frames is evident:

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

The following video demonstrates the need of multiple stack frames for a non-tail recursive program:

As the above function is non-tail recursive, the need for multiple stack frames makes sense. But, what about the following function?

int fact(int n, int result) 
{
     if (n == 1) 
         return result;
     else 
         return fact(n-1, n * result);    
}

The above function is tail recursive, hence tail call optimization is possible. The following video demonstrates how a single stack frame is enough to compute the final result in case of tail recursive functions: 

With this, I hope now it makes sense how tail call optimization works.

Benefits of Tail Call Optimization

• Prevention of stack overflow:  the possibility of stack overflow is eliminated because only one stack frame is used for multiple function calls. 
• Reduced memory usage:  As only one stack frame is used, the memory requirements of a recursive program is reduced significantly.
• Performance improvements: As there is less overhead of maintaining the call stack, the overall performance is improved.

Important Points to Remember

• TCO is not guaranteed: compiler may choose not to apply tail call optimization depending upon the circumstances of the code.
• Not all recursive functions are tail recursive:  recursive functions where the last operation is a recursive call is called tail recursive. For tail recursive functions only tail call optimization is possible.

Conclusion

Tail call optimization is a powerful tool that improves performance of recursive functions, especially for reducing memory usage and stack overflow. If applied, it can improve the overall performance of recursive calls.