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?

In reply to Re: Re3: Rindolf, Perl 6 and Wish lists by demerphq
in thread Rindolf, Perl 6 and Wish lists by rob_au

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.