Tail vs. Non-Tail Recursion

Tail Recursion

A recursive function is called tail recursive if the function call is the last thing to do. This means there is no computation after the function call.

A simple example to demonstrate this concept is as follows:

#include <stdio.h>

int fun(int n)
{
    if (n == 1)
        return 1;
    else
        return fun(n-1);
}

int main()
{
    printf("%d", fun(3));
}

Output:

1

Explanation:

The function fun() is called with value 3 from the main() function. Within the fun() function, the base case is satisfied only for n = 1. The function keeps calling itself until the base case is satisfied, and then it starts returning. The following illustration shows the stack diagram with multiple call frames:

You might have noticed that at the time of returning to the caller, there is no additional operation to perform. We are simply returning from one function to another. This is exactly what tail recursion is. Due to this reason, a tail recursive function can be transformed into an iterative loop which can lead to reduced stack frames and hence, the reduced memory usage. Also, the performance increases because of the less overhead in maintaining the call stack. This optimization is called the Tail Call Optimization (TCO) which is done by the compiler.

Characteristics of Tail Recursion

Following are the characteristics of tail recursion:

• The recursive call is the final action.
• No further computation after the recursive call.
• Optimization is possible.

Practical Example of Tail Recursion

We discussed the factorial program in which the recursive procedure is not tail recursive because the multiplication operation needs to be performed every time we return from the function. As the recursive call is not the last operation, therefore, the original factorial program is not tail recursive. But, it doesn’t mean we cannot write the tail recursive version of the factorial program. The following program calculates the factorial of a number using tail recursion:

#include <stdio.h>

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

int main()
{
    printf("%d", fact(5, 1));
    return 0;
}

Output:

120

Explanation:

The above program is successfully calculating the factorial of a number using tail recursion. In this recursive procedure, we have the second argument acc (called the accumulator) which holds the ongoing product of the numbers as the function recurses. It is initialized to 1. 

The process is as follows:

• For the first time, fact(5, 1) is called from the main() function. 
• Within the fact(5, 1) function, the fact(4, 5) is called. It can be observed that the initial value of the accumulator (acc) is multiplied to n which is 5. 
• Now, within fact(4, 5), the fact() function is called with arguments 3 and 5 * 4 = 20. This means fact(3, 20). Can you see how nicely the product is calculated with each recursive call? This is what makes tail recursion possible as we don’t want to perform calculations when we start returning from functions, therefore, we need to do calculations when we recurse. 
• Now within function fact(3, 20), fact(2, 60) is called. In the same way, fact(1, 120) is called. 
• Within fact(1, 120), the base case condition is true because n = 1. Now, interestingly, we are not returning the value 1 in contrast to the original non-tail recursive factorial function. We are instead returning the value of the accumulator (acc). And, this value will eventually return to the main() without further calculations. 
• The final result is 120 which is the value of factorial of 5. 

Advantages and Disadvantages of Tail Recursion

Advantages

• Optimized performance:  Tail recursion can be transformed into a loop by the compiler, reducing the overhead of multiple recursive calls. This is called Tail Call Optimization (TCO) discussed in this tutorial in detail. 
• Memory efficiency:  it minimizes the use of stack space if TCO is applied. This makes tail recursive programs more memory efficient. 

Disadvantages

• Limited optimization support:  not all compilers support tail call optimization on all platforms, and hence tail recursive programs may not offer benefit in terms of stack space usage compared to non-tail recursion.
• Not always natural:  for some problems, converting a non-tail recursive program to tail recursive may not be straightforward or may complicate the logic of the program. 
• Stack overflow risk without optimization:  if the Tail Call Optimization (TCO) is not performed by the compiler, then the risk of stack overflow remains just like non-tail recursion. 

When to Use Tail Recursion

• When performance and memory usage is critical and when it is possible to write the tail recursion for a problem. 
• In languages or environments where the Tail Call Optimization (TCO) is possible. Otherwise, writing the tail recursive solution to a problem will not any benefit. 

Non-Tail Recursion

Non-Tail Recursion refers to a recursive procedure where a recursive call is not the last thing. There is at least some computation that needs to be performed when returning from the functions.

Example:

#include <stdio.h>

int fun(int n)
{
    if (n == 1)
        return 1;
    else
        return 1 + fun(n-1);
}

int main()
{
    printf("%d", fun(3));
    return 0;
}

Output: 

3

Explanation:

The program is similar to the program discussed in tail recursion. The only difference is that 1 (one) is added to the function call in the recursive case. Due to this, the recursive call is not the last operation. 

You can easily verify why the final result is 3. 

Characteristics of Non-Tail Recursion

• The recursive call is followed by additional operations. 
• It is not easily optimized by the compiler for performance.

Practical Examples of Non-Tail Recursion

The original factorial and Fibonacci programs are examples of non-tail recursion. Follow the links to learn more:

1. Finding the factorial of a number. 
2. Finding the nth Fibonacci number.

Advantages and Disadvantages of Non-Tail Recursion

Advantages

• Intuitive solution to some problems:  usually non-tail recursive solution for some problems is intuitive and straightforward especially for problems like tree traversal, factorial calculation, or solving combinatorial problems like permutations and combinations. 
• Flexibility:  it does not bind us with the fact that we cannot perform computations after the recursive call, thus gives us more flexibility. 

Disadvantages 

• Higher memory usage:  tail call optimization is not possible in case of non-tail recursive programs, and hence there us no possibility of reducing the stack space usage. 
• Potential performance hit:  due to the overhead of maintaining multiple stack frames, non-tail recursion can be slower than tail recursion, especially in cases where the recursion depth is significant. 

No tail call optimization:  as recursive call is not the last operation, compilers can’t optimize it into an iterative loop.

When to Use Non-Tail Recursion

• When the problem can be naturally solved using non-tail recursion. 
• When you know the chances of call stack overflow is thin. 
• When in languages or environments, tail call optimization is not supported.

Summary

The following table summarizes what we have learned so far.

Test your understanding

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

#include <stdio.h>

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

int main()
{
    printf("%d", fun(10, 0));
    return 0;
} 

Your score is out of