Tail Recursion in Data Structure

Tail Recursion:

A recursion function is said to be Tail Recursion if there are no pending operations to be performed on return from a recursive call.

Consider the function fnFact() of the algorithm, note that there is a pending operation, namely multiplication to be performed on return from each recursive call. Whenever there is a pending operation, the function says non-tail recursive. The fnFact() function can re-write in a tail-recursive way as shown below:

Algorithm:

Algorithm fnFact(n, result)
{
 if(n==0 || n==1)
 return result;
 else
 return fnFact(n-1, n*result);
}

Tail Recursion Example:

The above algorithm shows how the algorithm works. From this example, it is clear that there is no pending operation after return from any function call. In the above algorithm, assume that the factorial value of 3 is to be calculated. Then the function fnFact() said fnFact(3, 1). Now the question is how does the algorithm work?

The first condition of line 6 executes. As n=3, so, the program control goes to line 9 of the else part. Now the function fnFact(3, 1) calls itself but with different parameters like fnFact(2, 3). Similarly, fnFact(2, 3) calls fnFact(1, 6). Now, as n=1, the function fnFact(1, 6) returns 6 to fnFact(2, 3) and so on. Thus we can implement a factorial function in a tail-recursive way.