What is tail recursion?

Question

While learning lisp, I've come across the term *tail-recursive*. What does it mean exactly?

Answer 1

Tail recursion is recursion where the function calls itself at the end of the function.

Since I don't know how familiar you are with the concept - let's start with recursion.

Recursive functions are functions that call themselves.

Example:

Here we have an algorithm to calculate a factorial.

A factorial is a number multiplied by itself and all the integers below it.

So factorial 3 (3!) is equal to 6 (3 x 2 x 1).

factorial 4 (4!) is equal to 24 (4 x 3 x 2 x 1).

factorial 5 (5!) is equal to 120 (5 x 4 x 3 x 2 x 1)

We can see that we can calculate the factorial by multiplying the number by the factorial of the integer one less than it. (ex 5 x 4! is equal to 5!)

So we can use recursion here!

Here the function calls itself as a part of the formula until it hits the base case . Once it hits the base case, it returns the base number - 1. (1! = 1)

function int factorial(int n){

if (n<=1){

return 1;

}

return n*fact(n-1);

}

Tail recursion is a recursive formula that calls itself at the end. So in the example above we can see that the LAST line is a call to the function itself - so it's a tail recursive function.

Now why do we want to use tail recursion? Well, what happens when DON'T call the function as the last line vs when the recursive call is the last line?

ex

function int r(num){

if (num<1){return 1;} //base case

else{ int ret = r(num-1); }//recursive call

int temp;

//some calculations

return ret;

}

here one of the first things it does is go into the next function.

r(3)->r(2)->r(1)->r(1)calculations->return to r(2) and r(2) calculations ->return and r(3) calculations -> return value to main function.

Here we can tell that it starts with r(3) but eventually has to return/end on r(3) to finish the calculations;

if you restructure it so it's tail recursive, what happens?

function int r(num){

int temp;

if (num<1){return 1;} //base case

//some calculations

return temp + r(num-1);//recursive call

}

Let's see what happens?

r(3) calculations -> r(2) calculations -> r(1)

return to main <--return <---return

Here all the calculations are done in order and all we're left with is returning the value. This makes the calculation and algorithm faster and more efficient. This is an example of why we choose tail recursion and what it is.