We learned the concept of recursion in our previous tutorials where we understood that a recursive procedure allows us to divide a big problem into smaller subproblems. While understanding the basics of recursion is crucial, it is equally important to understand different types of recursion–tail and non-tail recursion–as they are different in terms of overall performance and memory usage. This tutorial delves deeper into these concepts exploring definitions, differences, and when to use what. So, let’s dive in.

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:

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.

Aspect

Tail Recursion

Non-Tail Recursion

Final operation

Recursive call

Additional operations follow the recursive call

Memory efficiency

More memory efficient due to Tail Call Optimization (TCO)

Less memory efficient; each call adds a stack frame to the call stack

Performance

Generally faster when optimized because of less overhead to maintain the call stack

Slower due to the overhead of maintaining the call stack

Use cases

Best for problems that can be expressed iteratively

Suitable for problems requiring post-recursive computation

Example

Tail-recursive factorial

Standard Non-Tail recursive factorial

Test your understanding

Question 1

Which of the following statements about the tail recursion is true?

The recursive call must be the first statement in the function.

Tail recursion performs additional operations after the recursive call.

Tail recursion is very slow.

Tail recursion allows optimization to reuse the current stack frame, thus saving memory.

explanation

For a tail-recursive program, there is the possibility of tail call optimization which helps in reducing the number of stack frames. This reduces the burden of maintaining the call stack.

Question 2

Consider the following function:

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

What is the primary feature of this function?

It is non-recursive.

It is a non-tail recursive function.

It is a tail-recursive function.

None of the above

explanation

There is no further computation after the recursive call fun(n-1, acc + n). As the recursive call is the last operation, therefore, the given function is a tail-recursive function.

Question 3

Consider the following program with the same function as in the previous question:

#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;
}

What is the output of the above program?

55

0

Compilation error

None of the above

explanation

The function is calculating the sum of first n natural numbers. In our program, the value of n is 10 and acc (which will hold the final result) is initialized to 0. Everytime the function is called, the current value of n is added to the accumulator (acc). With each function call, the value of n is decreased by 1, so eventually all numbers from n to 1 are added. This is equivalent to the sum of n natural numbers.

## Leave a comment