Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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
5  
Look at "What is tail-recursion?" on stackoverflow –  Vor Oct 22 '12 at 9:24
2  
@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
1  
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

4 Answers 4

up vote 11 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.