What is Tail Recursion?

Recursion

I think we all understand what recursion is without any explanation. If you do not really know what recursion is the best way to know is to do a google search of the word recursion.

Love┬áthat Google Easter egg ­čÖé

Anyway. Since we all know what recursion is let’s try to understand why in quite a few cases. Recursion is considered as bad programming. Even though many solutions to problems we face in real life computing are inherently recursive most of the recursive solutions are also inherently bad as they either consume too much memory, or the loop solution is much more efficient in terms of speed.

In our examples here we will try to solve the classic problem of finding the factorial of a number.
If you do not know what the factorial means in terms of math (I only accept the excuse of non-native English speaker, other than that you suck at math so you do not deserve to be a software developer unless you get some real knowledge in your brain) let me explain:

The factorial of a non negative Integer is the product of multiplying all the positive numbers
preceding and including that Integer.

e.g.

4!= 4*3*2*1
10!=10*9*8*7*6*5*4*3*2*1

Now as one can thin this is simple to solve using loop logic and it could be done like the following piece of code

Could you think of the Recursive solution to this problem? I don’t think it’s pretty difficult right? It would be more something like the following:

Simple right? Now let’s compare the efficiency of the two solutions. Using the following code we measure the efficiency of the two algorithms

Comparing the two outputs we will see that they only have 1ms difference in terms of speed. (Let’s ignore the fact that the result will reach an overflow and end up to be zero for a moment here).

What happens though if we increase the number? What possibly could be the outocome?
Well if we try to calculate the factorial of the number 10000 we get a StackOverflowException using the Recursive method.
So what happens here?
Well for every method call a new stack frame is created in memory to store the variables. In a recursive call in a method a new stack frame is created in the memory to store for each recursive call. So with many recursive calls the stackframe might end up being completely full which will lead our application to crash. There of course ways to reduce the need of this extra stack frames. How? Well by introducing Tail Recursion.

What is Tail Recursion?

Tail recursion is using recursion as the final call of a method that will include no more actions after that. For example, in our recursive Factorial Solution after the recursive call to factorial we multiply the result with the current number. Let’s transform our recursive Factorial to a tail recursive Factorial.

So what is the benefit of all this? Well it’s actually pretty simple. If you look at our return statement, it no longer has any calculations to be done after the call to the recursive method is completed. Which means that by doing this we simply remove the need for an extra stack frame to be stored in memory, thus reducing the memory footprint of our code.
A smart compiler can really recognize this and not allocating a new stack frame for every recursive call.

In many languages, the compiler in fact does this if it sees the above type of code. Some convert it to a jump call while others can really convert to a loop directly.

But in two widely popular languages, C# and Java, this is not implemented yet as there issues with the Garbage collector. It is in the works but not yet implemented as it’s not a top priority for either of the two languages. But if you are using a language like Javascript (ES 6), C or C++ ┬áthen it is implemented and you can really make use of this.

Leave a Reply