Tail Call, Tail Recursion and Tail Call Optimization

Tail Call
 
Tail Call happens when a function returns a value which is the immediate return value of another function. For instance, here is a tail call:

 
In this code, func1 returns the immediate return value of func2. Thus the invoking of func2 is in the tail position.
 
Tail Recursion
 
Tail Recursion happens when a function returns a value which is the immediate return value of the same function but another instance. Here is an example of tail recursion:

 
This code results in an infinite number of function calls. Each instance of the function calls the same function again and return the value returned by the next instance.
 
Tail Call Optimization
 
When a function is invoked, a new stack frame is added to the call stack. Consider the same above function again:

 
When you invoke func1 from your main function, a stack frame is added. func1 further calls func2, thus adding one more stack frame to the call stack. func1 returns a value only after func2 returns its value. So the stack frame of func1 stays in memory until execution func2 is finished. But as it is a tail call, this is not required. The stack frame of func1 can be replaced by func2 because no more processing is done in func1.  In simple terms, it works as a goto statement with parameters.
 
The process of identifying tail call and replacing stack frame, thus reducing memory usage is called Tail Call Optimization.  Tail Call Optimization makes it possible to run recursive functions as fast as iteration.
 
Example: Program to find a factorial
 
In a previous post, I explained how to write a program to find factorial using recursion. Here is the program:

 
This is NOT a tail call. It doesn’t just return the value returned by next function. But it gets the return value, multiplies and then returns. Thus a processing is done and thus this is not a tail call and performs slower. Let us look how to implement the same using tail calls:

 
The function calls in the order will be like
fact(4,1)
fact(3,4)
fact(2,12)
fact(1,24)
fact(0,24)
 
Here we’ve used a different logic here to suite our program to tail recursion. This program uses less memory than the previous program because each time, the fact function is invoked, the stack trace of previous instance is cleared and replaced with the new one.

Leave a Reply

Your email address will not be published. Required fields are marked *