algorithm java - What is tail recursion?




non python (20)

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


Answers

A tail recursion is a recursive function where the function calls itself at the end ("tail") of the function in which no computation is done after the return of recursive call. Many compilers optimize to change a recursive call to a tail recursive or an iterative call.

Consider the problem of computing factorial of a number.

A straightforward approach would be:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Suppose you call factorial(4). The recursion tree would be:

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

The maximum recursion depth in the above case is O(n).

However, consider the following example:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

Recursion tree for factTail(4) would be:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

Here also, maximum recursion depth is O(n) but none of the calls adds any extra variable to the stack. Hence the compiler can do away with a stack.


Tail recursion is the life you are living right now. You constantly recycle the same stack frame, over and over, because there's no reason or means to return to a "previous" frame. The past is over and done with so it can be discarded. You get one frame, forever moving into the future, until your process inevitably dies.

The analogy breaks down when you consider some processes might utilize additional frames but are still considered tail-recursive if the stack does not grow infinitely.


Here is a quick code snippet comparing two functions. The first is traditional recursion for finding the factorial of a given number. The second uses tail recursion.

Very simple and intuitive to understand.

Easy way to tell if a recursive function is tail recursive, is if it returns a concrete value in the base case. Meaning that it doesn't return 1 or true or anything like that. It will more then likely return some variant of one of the method paramters.

Another way is to tell is if the recursive call is free of any addition, arithmetic, modification, etc... Meaning its nothing but a pure recursive call.

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

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).


Here is a Common Lisp example that does factorials using tail-recursion. Due to the stack-less nature, one could perform insanely large factorial computations ...

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

And then for fun you could try (format nil "~R" (! 25))


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
}

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.


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.


This question has a lot of great answers... but I cannot help but chime in with an alternative take on how to define "tail recursion", or at least "proper tail recursion." Namely: should one look at it as a property of a particular expression in a program? Or should one look at it as a property of an implementation of a programming language?

For more on the latter view, there is a classic paper by Will Clinger, "Proper Tail Recursion and Space Efficiency" (PLDI 1998), that defined "proper tail recursion" as a property of a programming language implementation. The definition is constructed to allow one to ignore implementation details (such as whether the call stack is actually represented via the runtime stack or via a heap-allocated linked list of frames).

To accomplish this, it uses asymptotic analysis: not of program execution time as one usually sees, but rather of program space usage. This way, the space usage of a heap-allocated linked list vs a runtime call stack ends up being asymptotically equivalent; so one gets to ignore that programming language implementation detail (a detail which certainly matters quite a bit in practice, but can muddy the waters quite a bit when one attempts to determine whether a given implementation is satisfying the requirement to be "property tail recursive")

The paper is worth careful study for a number of reasons:

  • It gives an inductive definition of the tail expressions and tail calls of a program. (Such a definition, and why such calls are important, seems to be the subject of most of the other answers given here.)

    Here are those definitions, just to provide a flavor of the text:

    Definition 1 The tail expressions of a program written in Core Scheme are defined inductively as follows.

    1. The body of a lambda expression is a tail expression
    2. If (if E0 E1 E2) is a tail expression, then both E1 and E2 are tail expressions.
    3. Nothing else is a tail expression.

    Definition 2 A tail call is a tail expression that is a procedure call.

(a tail recursive call, or as the paper says, "self-tail call" is a special case of a tail call where the procedure is invoked itself.)

  • It provides formal definitions for six different "machines" for evaluating Core Scheme, where each machine has the same observable behavior except for the asymptotic space complexity class that each is in.

    For example, after giving definitions for machines with respectively, 1. stack-based memory management, 2. garbage collection but no tail calls, 3. garbage collection and tail calls, the paper continues onward with even more advanced storage management strategies, such as 4. "evlis tail recursion", where the environment does not need to be preserved across the evaluation of the last sub-expression argument in a tail call, 5. reducing the environment of a closure to just the free variables of that closure, and 6. so-called "safe-for-space" semantics as defined by Appel and Shao.

  • In order to prove that the machines actually belong to six distinct space complexity classes, the paper, for each pair of machines under comparison, provides concrete examples of programs that will expose asymptotic space blowup on one machine but not the other.


(Reading over my answer now, I'm not sure if I'm managed to actually capture the crucial points of the Clinger paper. But, alas, I cannot devote more time to developing this answer right now.)


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

Here is a simple JavaScript implementation that uses recursion:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

If you called recsum(5), this is what the JavaScript 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 JavaScript interpreter begins to actually do the work of calculating the sum.

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

function 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: The original answer used examples from Python. These have been changed to JavaScript, since modern JavaScript interpreters support tail call optimization but Python interpreters don't.


This is an excerpt from Structure and Interpretation of Computer Programs about tail recursion.

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process.

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while. The implementation of Scheme does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.


In short, a tail recursion has the recursive call as the last statement in the function so that it doesn't have to wait for the recursive call.

So this is a tail recursion i.e. N(x - 1, p * x) is the last statement in the function where the compiler is clever to figure out that it can be optimised to a for-loop (factorial). The second parameter p carries the intermediate product value.

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

This is the non-tail-recursive way of writing the above factorial function (although some C++ compilers may be able to optimise it anyway).

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

but this is not:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

I did write a long post titled "Understanding Tail Recursion – Visual Studio C++ – Assembly View"


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.


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.


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)). 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 snicker with a tail recursive call. Simply reuse the current stack frame for the next recursive step. I'm pretty sure Lisp does this.


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.


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

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

is equivalent to the tail-recursive function(s)

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

sum(n) {
  return sum_aux(n,1,0);
}

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


To understand some of the core differences between tail-call recursion and non-tail-call recursion we can explore the .NET implementations of these techniques.

Here is an article with some examples in C#, F#, and C++\CLI: Adventures in Tail Recursion in C#, F#, and C++\CLI.

C# does not optimize for tail-call recursion whereas F# does.

The differences of principle involve loops vs. Lambda calculus. C# is designed with loops in mind whereas F# is built from the principles of Lambda calculus. For a very good (and free) book on the principles of Lambda calculus, see: Structure and Interpretation of Computer Programs, by Abelson, Sussman, and Sussman.

Regarding tail calls in F#, for a very good introductory article , see: Detailed Introduction to Tail Calls in F#. Finally, here is an article that covers the difference between non-tail recursion and tail-call recursion (in F#): Tail-recursion vs. non-tail recursion in F sharp.

If you want to read about some of the design differences of tail-call recursion between C# and F#, see: Generating Tail-Call Opcode in C# and F#.

If you care enough to want to know what conditions prevent the C# compiler from performing tail-call optimizations, see this article: JIT CLR tail-call conditions.


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, depending on language the compiler may be able to collapse the stack down to one entry, so you save stack space...A large recursive query can actually cause a .

Basically Tail recursions are able to be optimized into iteration.


Let's walk through a simple example: the factorial function implemented in C.

We start with the obvious recursive definition

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

A function ends with a tail call if the last operation before the function returns is another function call. If this call invokes the same function, it is tail-recursive.

Even though fac() looks tail-recursive at first glance, it is not as what actually happens is

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

ie the last operation is the multiplication and not the function call.

However, it's possible to rewrite fac() to be tail-recursive by passing the accumulated value down the call chain as an additional argument and passing only the final result up again as the return value:

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

Now, why is this useful? Because we immediately return after the tail call, we can discard the previous stackframe before invoking the function in tail position, or, in case of recursive functions, reuse the stackframe as-is.

The tail-call optimization transforms our recursive code into

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

This can be inlined into fac() and we arrive at

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

which is equivalent to

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

As we can see here, a sufficiently advanced optimizer can replace tail-recursion with iteration, which is far more efficient as you avoid function call overhead and only use a constant amount of stack space.





algorithm language-agnostic functional-programming recursion tail-recursion