# What is tail recursion?

I know the general concept of recursion. I came across the concept of tail recursion while studying the quicksort algorithm. In this video of quick sort algorithm from MIT at 18:30 seconds the professor says that this is a tail recursive algorithm. It is not clear to me what tail recursion really means.

Can someone explain the concept with a proper example?

Some answers provided by the SO community here.

-
Tell us more about the context where you have encountered the term tail recursion. Link? Citation? – A.Schulz Oct 22 '12 at 9:05
@A.Schulz I have put the link to the context . – Geek Oct 22 '12 at 9:18
Look at "What is tail-recursion?" on stackoverflow – Vor Oct 22 '12 at 9:24
@ajmartin The question is borderline on Stack Overflow but firmly on-topic on Computer Science, so in principle Computer Science should produce better answers. It hasn't happened here, but it's still ok to re-ask here in the hope of a better answer. Geek, you should have mentioned your earlier question on SO though, so that people don't repeat what's already been said. – Gilles Jan 5 '13 at 15:59
Also you should say what is ambiguous part or why you are not satisfied by previous answers, I think on SO people provide good answers but what caused you to ask it again? – user742 Jan 7 '13 at 10:14

Tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call. For example, the function

int f(int x, int y) {
if (y == 0) {
return x;
}

return f(x*y, y-1);
}


is tail recursive (since the final instruction is a recursive call) whereas this function is not tail recursive:

int g(int x) {
if (x == 1) {
return 1;
}

int y = g(x-1);

return x*y;
}


since it does some computation after the recursive call has returned.

Tail recursion is important because it can be implemented more efficiently than general recursion. When we make a normal recursive call, we have to push the return address onto the call stack then jump to the called function. This means that we need a call stack whose size is linear in the depth of the recursive calls. When we have tail recursion we know that as soon as we return from the recursive call we're going to immediately return as well, so we can skip the entire chain of recursive functions returning and return straight to the original caller. That means we don't need a call stack at all for all of the recursive calls, and can implement the final call as a simple jump, which saves us space.

-
you wrote "That means we don't need a call stack at all for all of the recursive calls" . Call stack will always be there , just that the return address need not be written into the call stack , right ? – Geek Jan 8 '13 at 5:09
It depends on your model of computation to some degree :) But yes, on a real computer the call stack is still there, we're just not using it. – Matt Lewis Jan 8 '13 at 11:25

My answer is based on the explanation given in the book Structure and Interpretation of Computer Programs. I highly recommend this book to computer scientists.

Approach A: Called as a Linear Recursive Process

(define (factorail n)
(if (= n 1)
1
(* n (factorial (- n 1)))))


Shape of the process for Approach A looks like this:

(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120


Approach B: Called as Linear Iterative Process

(define (factorial n)
(fact-iter 1 1 n))

(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))


Shape of the process for Approach B looks like this:

(factorial 5)
(fact-iter 1 1 5)
(fact-iter 1 2 5)
(fact-iter 2 3 5)
(fact-iter 6 4 5)
(fact-iter 24 5 5)
(fact-iter 120 6 5)
120


The Linear Iterative Process (Approach B) runs in constant space even though the process is a recursive procedure. It should also be noted that in this approach a set variables define the state of the process at any point viz. {product, counter, max-count}. This is also a technique by which tail recursion allows compiler optimization.

In Approach A there is more hidden information which the interpreter maintains which is basically the chain of deferred operations.

-

Simply said, tail recursion is a recursion where the compiler could replace the recursive call with a "goto" command, so the compiled version will not have to increase the stack depth.

Sometimes designing a tail-recursive function requires you need to create a helper function with additional parameters.

For example, this is not a tail-recursive function:

int factorial(int x) {
if (x > 0) {
return x * factorial(x - 1);
}
return 1;
}


But this is a tail-recursive function:

int factorial(int x) {
return tailfactorial(x, 1);
}

int tailfactorial(int x, int multiplier) {
if (x > 0) {
return tailfactorial(x - 1, x * multiplier);
}
return multiplier;
}


because the compiler could rewrite the recursive function to a non-recursive one, using something like this (a pseudocode):

int tailfactorial(int x, int multiplier) {
start:
if (x > 0) {
multiplier = x * multiplier;
x--;
goto start;
}
return multiplier;
}


The rule for the compiler is very simple: When you find "return thisfunction(newparameters);", replace it with "parameters = newparameters; goto start;". But this can be done only if the value returned by the recursive call is returned directly.

If all recursive calls in a function can be replaced like this, then it is a tail-recursive function.

-

Tail-recursion is a form of recursion in which the recursive calls are the last instructions in the function (that's where the tail part comes from). Moreover, the recursive call must not be composed with references to memory cells storing previous values (references other than the parameters of the function). In this way, we don't care about previous values and one stack frame suffices for all of the recursive calls; tail-recursion is one way of optimizing recursive algorithms. The other advantage/optimization is that there is an easy way to transform a tail-recursive algorithm to an equivalent one that uses iteration instead of recursion. So yes, the algorithm for quicksort is indeed tail-recursive.

QUICKSORT(A, p, r)
if(p < r)
then
q = PARTITION(A, p, r)
QUICKSORT(A, p, q–1)
QUICKSORT(A, q+1, r)


Here is the iterative version:

QUICKSORT(A)
p = 0, r = len(A) - 1
while(p < r)
q = PARTITION(A, p, r)
r = q - 1

p = 0, r = len(A) - 1
while(p < r)
q = PARTITION(A, p, r)
p = q + 1

-