------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Tail recursion is the most trivial form of recursion. It is when the last statement in a function/subroutine calls itself. (Or more complicated when the last statement calls another function whose last statement calls the first... etc).

The reason I say trivial is becuase it is the form of recursion that can be easily mechanically converted into iteration. As most programmers know there is nothing that can be implemented using recursion that cant be implemented using iteration (and usually way more efficiently), but that some algorithms are far more suited to one or the other.

A good example would be a breadth first versus depth first traversal of a data structure. BF is far easier to code as an iterative function and DF as a recursive function.

So why does all this matter? Well, because Tail Recusion is used in many languages that do not want to provide proper looping structures. So when the language encounters tail recursion it internally converts it to the far more efficient iteration, transparently to the user.

Optimizing compilers will when they see a function that looks like this:

sub foo {
  my $x=shift;
  #code....
  foo($x+1);
}
[download]

will usually optimize it into something like this:

sub foo {
  my $x=shift;
START_OF_FOO:
  #code
  $x++;
  goto START_OF_FOO;
}
[download]

Which avoids the overhead of the stack, and is thus much more efficient.

The rub of this is that "Tail Recursion" is one of those jargony terms that people that dont know that much love to throw around without realizing that they are talking about something that is in essence trivial and or obvious or whatever.

Oh and the reason you probably dont hear much about it in the perl world is that we have plethora of excellent looping structures, and we use them. However I seem to recall hearing that perl does handle Tail Recursion optimization, so use it if you wish.

Anyway, heres a couple of links regarding tail recursion... Some of them probably dont entirely agree with my opinion, but thats a good thing. :-)

Dictionary of Algorithms and Data Structures

A lispy point of view

Jargon ref

Even better jargon :-)

A good one (takes a while to load though, be patient.

Yves / DeMerphq
--
When to use Prototypes?