What is tail recursion?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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: Linear Recursive Process

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

The 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: 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.

Answer 4

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