What is tail-recursion?

Question

Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean?

Answer 1

I'm not a Lisp programmer, but I think this will help.

Basically it's a style of programming such that the recursive call is the last thing you do.

Answer 2

Using regular recursion, each recursive call pushes another entry onto the call stack. When the recursion is completed, the app then has to pop each entry off all the way back down.

With tail recursion, the compiler is able to collapse the stack down to one entry, so you save stack space...A large recursive query can actually cause a stack overflow.

Basically Tail recursions are able to be optimized into iteration.

Answer 3

Tail recursion refers to the recursive call being last in the last logic instruction in the recursive algorithm.

Typically in recursion you have a base-case which is what stops the recursive calls and begins popping the call stack. To use a classic example, though more C-ish than Lisp, the factorial function illustrates tail recursion. The recursive call occurs after checking the base-case condition.

factorial(x, fac) {

  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

Note, the initial call to factorial must be factorial(n, 1) where n is the number for which the factorial is to be calculated.

Answer 4

In traditional recursion, the typical model is that you perform your recursive calls first, and then you take the return value of the recursive call and calculate the result. In this manner, you don't get the result of your calculation until you have returned from every recursive call.

In tail recursion, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of "(return (recursive-function params))" (I think that's the syntax for Lisp). Basically, the return value of any given recursive step is the same as the return value of the next recursive call.

The consequence of this is that once you are ready to perform your next recursive step, you don't need the current stack frame any more. This allows for some optimization. In fact, with an appropriately written compiler, you should never have a stack overflow snicker with a tail recursive call. Simply reuse the current stack frame for the next recursive step. I'm pretty sure Lisp does this.

Answer 5

Instead of explaining it with words, here's an example. This is a Scheme version of the factorial function:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

Here is a version of factorial that is tail-recursive:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

You will notice in the first version that the recursive call to fact is fed into the multiplication expression, and therefore the state has to be saved on the stack when making the recursive call. In the tail-recursive version there is no other S-expression waiting for the value of the recursive call, and since there is no further work to do, the state doesn't have to be saved on the stack. As a rule, Scheme tail-recursive functions use constant stack space.

Answer 6

The jargon file has this to say about the definition of tail recursion:

tail recursion /n./

If you aren't sick of it already, see tail recursion.

Answer 7

This excerpt from the book Programming in Lua ( http://www.lua.org/pil/6.3.htm ) shows how to make a proper tail recurssion (in Lua, but should apply to Lisp too) and why it's better.

A tail call [tail recursion] is a kind of goto dressed as a call. A tail call happens when a function calls another as its last action, so it has nothing else to do. For instance, in the following code, the call to g is a tail call:

function f (x)
  return g(x)
end

After f calls g, it has nothing else to do. In such situations, the program does not need to return to the calling function when the called function ends. Therefore, after the tail call, the program does not need to keep any information about the calling function in the stack.

Because a proper tail call uses no stack space, there is no limit on the number of "nested" tail calls that a program can make. For instance, we can call the following function with any number as argument; it will never overflow the stack:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

As I said earlier, a tail call is a kind of goto. As such, a quite useful application of proper tail calls in Lua is for programming state machines. Such applications can represent each state by a function; to change state is to go to (or to call) a specific function. As an example, let us consider a simple maze game. The maze has several rooms, each with up to four doors: north, south, east, and west. At each step, the user enters a movement direction. If there is a door in that direction, the user goes to the corresponding room; otherwise, the program prints a warning. The goal is to go from an initial room to a final room.

This game is a typical state machine, where the current room is the state. We can implement such maze with one function for each room. We use tail calls to move from one room to another. A small maze with four rooms could look like this:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

So you see, when you make a recursive call like:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

This is not tail recursive because you still have things to do (add 1) in that function after the recursive call is made. If you input a very high number it will probably cause a stack overflow.

Answer 8

An important point is that tail recursion is essentially equivalent to looping. It's not just a matter of compiler optimization, but a fundamental fact about expressiveness. This goes both ways: you can take any loop of the form

while(E) { S }; return Q

where E and Q are expressions and S is a sequence of statements, and turn it into a tail recursive function

f() = if E then { S; return f() } else { return Q }

Of course, E, S, and Q have to be defined to compute some interesting value over some variables. For example, the looping function

fibo(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

is equivalent to the tail-recursive function(s)

fibo_aux(n,i,k) {
  if( i <= n ) {
    return fibo_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

fibo(n) {
  fibo_aux(n,1,0);
}

(This "wrapping" of the tail-recursive function with a function with fewer parameters is a common functional idiom.)

Answer 9

Tail recursion is well-described in previous answers, but I think an example in action would help to illustrate the concept.

Consider a simple function that adds the first N integers. (e.g. sum(5)=1+2+3+4+5=15).

Here is a simple Python implementation that uses recursion:

def recsum(x):
 if x==1:
  return x
 else:
  return x+recsum(x-1)

If you called recsum(5), this is what the Python interpreter would evaluate.

recsum(5)
5+recsum(4)
5+(4+recsum(3))
5+(4+(3+recsum(2)))
5+(4+(3+(2+recsum(1))))
5+(4+(3+(2+1)))
15

Note how every recursive call has to complete before the Python interpreter begins to actually do the work of calculating the sum.

Here's a tail-recursive version of the same function:

def tailrecsum(x,running_total=0):
 if x==0:
  return running_total
else:
  return tailrecsum(x-1,running_total+x)

Here's the sequence of events that would occur if you called tailrecsum(5), (which would effectively be tailrecsum(5,0), because of the default second argument).

tailrecsum(5,0)
tailrecsum(4,5)
tailrecsum(3,9)
tailrecsum(2,12)
tailrecsum(1,14)
tailrecsum(0,15)
15

In the tail-recursive case, with each evaluation of the recursive call, the running_total is updated.

Note: As mentioned in the comments, Python doesn't have built-in support for optimizing away tail calls, so there's no advantage to doing this in Python. However, you can use a decorator to achieve the optimization.

Answer 10

It means that rather than needing to push the instruction pointer on the stack, you can simply jump to the top of a recursive function and continue execution. This allows for functions to recurse indefinitely without overflowing the stack.

I wrote a blog post on the subject, which has graphical examples of what the stack frames look like.

Answer 11

Recursion means a function calling itself. For example:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

Tail-Recursion means the recursion that conclude the function:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

See, the last thing un-ended function (procedure, in Scheme jargon) does is to call itself. Another (more useful) example is:

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

In the helper procedure, the LAST thing it does if left is not nil is to call itself (AFTER cons something and cdr something). This is basically how you map a list.

The tail-recursion has a great advantage that the interperter (or compiler, dependent on the language and vendor) can optimize it, and transform it into something equivalent to a while loop. As matter of fact, in Scheme tradition, most "for" and "while" loop is done in tail-recursion manner (there is no for and while, as far as I know).

Answer 12

here is a Perl 5 version of the tailrecsum function mentioned earlier.

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

Answer 13

In Java, here's a possible tail recursive implementation of the Fibonacci function:

public int tailRecursive(final int n) {
 if (n <= 2)
  return 1;
 return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
 if (iter == n)
  return acc;
 return tailRecursiveAux(n, ++iter, acc + iter);
}

Contrast this with the standard recursive implementation:

public int recursive(final int n) {
 if (n <= 2)
  return 1;
 return recursive(n - 1) + recursive(n - 2);
}

Answer 14

In normal recursion, there is at least two extra overhead.

1. Extra Time
2. Extra memory

Executing a method call and corresponding return statement usually takes longer than incrementing and testing a loop control variable. In addition, a method call ties up some memory that is not freed until the method completes its task because calculation is carried out after the recursive call.

In tail-recursive, the calculation is carried out before recursive call so the benefits are at least two.

1. No linear growth of method calls
2. No extra stack memory is required.

Example of tail-recursive algorithm to find out the value of factorial number e.g. 5!.

int factorial (int number){
  if (number == 0) return 1;
  else
  return aMethod (number, 1);
}

int aMethod (int currentNumber, int result){

if (currentNumber ==1) return result;
else
return aMethod(currentNumber-1, result* currentNumber);

}

But if we use normal recursion for above example to find out 5! or any number, we can use following code:

int aMethod (int n){
if (n<=1) return 1;
else
return n* aMethod (n-1);
}

In above (normal recursion) example, multiplication is performed after the recursive call, but in tail-recursive example (1st example), multiplication is performed before the recursive call of the method, when its parameters are evaluated. To convert recursion of the factorial method to a tail-recursive version, we need an additional parameter (in this case, int result) that passes the accumulated value of the factorial down on each recursive call. In the last call of the method, this value os returned as the result.

But mind it, some methods are difficult or impossible to convert to tail-recursive versions, and the compiler optimisations are not part of the standard definitions of many languages, among them, Java. If you find that your Java compiler supports this optimisation, you should try converting some methods to tail-recursive versions and see if they run faster than the original versions.