What is Tail Recursion? Provide an example and a simple explanation.

Here we provide a simple tutorial and example of a normal non-tail recursive solution to the Factorial problem in Java, and then we can also go over the same problem but use a tail recursive solution in Python. Don’t worry if you don’t know Python, the code is very intuitive and easy to understand even if you come from another background.

If you read our recursion tutorial, then you should already have a good idea of how the recursive solution for the factorial works. This is the Java code that will calculate the factorial of a number:

public int factorial (int x)
{
  if (x == 1)
  {
    return 1;  //base case
  }

  else  /*recursive case*/
   return factorial(x-1) * x;
}

Let’s say that we want to calculate the factorial of 4 using the function above. So, what exactly happens when the value of 4 is passed into the function above? Well, here is the sequence of calls that will be made – with the first to last going from top to bottom:

factorial (4) ;
return factorial(3) * 4;
return factorial(2) * 3;
return factorial(1) * 2;
return 1;




The thing that you should pay special attention to is the fact that in order to reach the final value of the factorial (which is 24), each and every function call must be executed to completion. You should be able to see that – in order to know the factorial of 4 we must find the factorial of 3 multiplied by 4, and in order to get the factorial of 3, we must get the factorial of 2 multiplied by 3, and in order to get the factorial of 2 we must get the factorial of 1 multiplied by 2, and finally, we know that the factorial of 1 is equal to 1 so 1 is returned because that is our base case which will actually stop the recursion. Then, a 2 will be returned (factorial(1) * 2 is equal to 2), and then a 6 will be returned by factorial(2) *3 and so on and so forth until the final value “24” is returned by the function.

The concept that we are trying to emphasize here is that every function call must run to completion in order for us to finally get to the correct value of “24”. This is different from tail recursion, and you will see why once we go over a variation of the factorial function that uses tail recursion.

Tail Recursion Factorial Implementation in Python

It’s much easier to understand tail recursion with an actual example followed by an explanation of that example. With that in mind, let’s go over an example of a Factorial solution in Python that uses tail recursion instead of normal recursion. We use Python because it’s easier for the sake of illustrating our example.

Example of Tail Recursion

def factorial(i, current_factorial=1):
  if i == 1:
    return current_factorial
  else:
    return factorial(i - 1, current_factorial * i)

Note that we provide a default argument of 1 for the current_factorial, but that only applies to the very first call of the function. When the factorial function is called recursively the default argument is overridden with whatever value is passed by the recursive call. We need to have that second argument there because it will hold the current factorial value which we intend on passing into the function.

Breaking down our example of tail recursion

Now, let’s suppose again that we want to calculate the factorial of 4. Note that the very first call to factorial(4) really is factorial(4, 1), because we have a default argument of 1 for the second parameter in factorial. So, we would end up with a series of calls that look like this:

factorial(4, 1)
return factorial (3,  1 * 4 ) //i == 4
return factorial (2,  4 *3 ) //i == 3
return factorial (1,  12 *2 ) //i == 2
return 24  //i == 1

So, you can see that each time the factorial function is called in our example, a new value for the current_factorial variable is passed into the factorial function. The function is basically updating the current_factorial variable with each call to the function. We are able to maintain the current factorial value because this function accepts 2 arguments/parameters – not just 1 like our normal, non-tail recursive factorial function above.

The difference between tail recursion and normal recursion




You can see that once we make a call to factorial (1, 12 *2 ), it will return the value of 24 – which is actually the answer that we want. The most important thing to notice about that is the fact that all of the recursive calls to factorial (like factorial (2, 4 *3 ), factorial (3, 1*4 ), etc) do not actually need to return in order to get the final value of 24 – you can see that we actually arrive at the value of 24 before any of the recursive calls actually return. So, we can say that a function is tail recursive if the final result of the recursive call – in this case 24 – is also the final result of the function itself, and that is why it’s called “tail” recursion – because the final function call (the tail-end call) actually holds the final result. If we compare that with our earlier example of “normal” recursion, you should see the difference – the “normal” recursive call is certainly not in it’s final state in the last function call, because all of the recursive calls leading up to the last function call must also return in order to actually come up with the final answer.

Tail recursion and stack frames

If you read our Recursion Tutorial, then you understand how stack frames work, and how they are used in recursion. We won’t go into detail here since you can just read that article, but basically each recursive call in a normal recursive function results in a separate stack frame as you can see in this graphic which assumes a call of Factorial(3) is being made:

Tail call optimization explanation

Tail call optimization is the process by which a tail recursive function call is optimized to use just one stack frame. You should definitely read our detailed explanation on tail call optimization here: Tail call optimization.

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

  • shubham randive

    thanx

  • Guest

    😛

  • de

    very helpful!

  • nn

    cool man