Tail Recursion Problem

In this article, we will discuss tail recursion. The tail recursion is that kind of recursion in which the recursive call is made at the end of the function. In other words, no statement exists after the recursive call.

Let us consider the following in C++ that demonstrates how tail recursion works:

Source Code:

Output:

Please note that in the above program there is no statement to be executed after the recursive call.

Need for the tail recursion

The tail recursion is always preferred over the non-tail recursion as the compiler can easily optimized tail recursion.

The compiler is generally responsible for executing recursive statements with the help of a stack. The stack keeps all the necessary information including the value of parameters for each and every recursive call. Whenever there is a call made to a procedure, the information is passed to the stack, and the moment when the execution of the function ends, the information is popped out or removed from the stack. So, the problem that persists with the non-tail recursion functions is that non-tail recursive functions take more stack depth as compared to tail recursion.

How the compiler optimizes tail recursion?

The tactic utilized by the compiler to optimize the tail recursion is simple. Actually, there is no statement to be executed after the tail recursive statement so the compiler doesn’t have to worry about saving the current function’s stack frame.

How to convert a non-tail recursion into tail recursion?

We can convert most of the non-tail recursive functions into tail recursion. For example, consider the following program that computes the sum of the first N natural numbers. The below program looks like a tail recursion but it is not actually. This is because first, we calculate the result of the operation myFunction(number + 1) and then apply the addition with the number and then return the entire value. So calling the recursive function is not the last thing being done here.

Source Code

Output:

We can easily convert the above non-tail recursion into tail recursion. The idea is to pass an additional argument to myFunction and return the recursive call as a whole at the end of the function. For example, consider the following that computes the sum of N natural numbers using tail recursion:

Source Code:

Output:

Conclusion

In this article, we discussed an important data structures concept, tail recursion. We believe that you must have learned something new through this article.