Before we get into the core, let's revise some basics.
Recursion : It is a process in which a function repeatedly calls itself until a base condition is not reached or a desired result is not achieved.
Base Condition : It is a condition when the function stops making recursive calls and starts returning the result. And if this condition is not defined, the program might get into infinite loop which will cause Stack Overflow Error as the stack memory will get wasted.
Stack Overflow Error : To have a better understanding about what this is refer to my article on How Functions Work Internally so that you can learn about program stack, stack frame and everything else. So, this error basically happens when the stack memory gets exhausted due to a large amount of incoming stack frames which can't be accommodated in the stack anymore.
So now let's get to the topic.
What is Tail Recursion ?
A recursive function is tail recursive when a recursive call is the last thing executed by the function. I know it didn't explained much about the topic. So let's see first what non-tail recursion is i.e. the traditional recursion that we all use mostly.
In traditional / non-tail recursion, the typical model is that you perform your recursive calls first, the you take the return value of the recursive calls and calculate the result. In this manner, you don't get the result of your calculation until you have returned from every recursive call. For ex:
main_function() {
//Calculating the sum of N natural numbers
int sum = nsum(5);
display sum;
}
int nsum(int x) {
if (x == 0) { //base condition
return 0;
}
else {
return (x + nsum(x - 1));
}
For the above pseudocode, the control flow will be like :
It can be said that for the result to be computed, each and every recursive call has to finish it's operation first.
Now, in tail recursion, you perform your calculations first, and then you execute the recursive call passing the result of your current step to the next step. So, the return value of any given recursive step is same as the return value of the next recursive call. Let's visualize it through the pseudocode and it's control flow.
main_function() {
//Calculating the sum of N natural numbers
int sum = nsum(0, 5);
display sum;
}
int nsum(int sum, int x) {
if (x == 0) { //base condition
return sum;
}
else {
return nsum(sum + x, x - 1);
}
The control flow goes like:
The consequence of tail recursion is that once the program is ready to perform the next recursive step, it doesn't need the current stack frame in the program stack anymore. This allows for some optimization as it can be seen from image (2) and (4) that the computation process of Tail Recursion takes much lesser time than the time taken by Non-Tail Recursion. With the tail recursive function, Stack Overflow Error might not be encountered.
That is all about Tail Recursion that you needed to know.
If you found the article interesting, please let me know in the comment section or if you have any doubts regarding it, please drop it in the same, I'll try to resolve it ASAP.
Thanks for reading ❤️