Tail Recursion Problem | Board Infinity

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:

// Header file
#include <bits/stdc++.h>
using namespace std;

// Function
void myFunction(int number)
{
// If n becomes greater than 10
// then return
if (number > 10)
return;

// Print the number
cout << " " << number;

// The last executed statement is recursive call
myFunction(number + 1);
}

// Main() function
int main() {

// Initialize an integer
int number = 1;

// Call myFunction
myFunction(number);
return 0;
}

Output:

write your code here: Coding Playground

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

// Header file
#include <bits/stdc++.h>
using namespace std;

// Function
int myFunction(int number)
{
// If n becomes equal to 10
// then return it
if (number == 10)
return number;

// Sum number with the result of myFunction(number + 1)
// and then return the entire value
return number + myFunction(number + 1);
}

// Main() function
int main() {

// Initialize an integer
int number = 1;

// Call myFunction
cout << myFunction(number);
return 0;
}

Output:

write your code here: Coding Playground

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:

// Header file
#include <bits/stdc++.h>
using namespace std;

// Function
int myFunction(int sum, int number)
{
// If n becomes greater than 10
// then return it
if (number > 10)
return sum;

// Just return the result of the
// recursive call
return myFunction(sum + number,number + 1);
}

// Main() function
int main() {

// Initialize an integer
int number = 1;

// Call myFunction
cout << myFunction(0, number);
return 0;
}

write your code here: Coding Playground

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.