What you describe as tail recursion is not exactly what is usually meant by tail recursion. Tail recursion refers to a specific simple optimization. Normally when one function calls another, you store a bunch of information for the call that is being made, do the other call, return the data, and process it more. But if the first function is just going to return the result of the second function, then there is little reason to keep intermediate information around, and you can just eliminate the current function call.

For instance consider the following to see the effect: 

sub loop {
  my ($from, $to, $action) = @_;
  if ($to < $from) {
    return;
  }
  else {
    $action->($from);
    loop($from+1, $to, $action);
  }
}

[download]
This is a recursive function that logically acts like a loop. But unlike a loop, calling it in Perl ties up memory with every function call, so doing a million iteration takes up both time and memory. But in a language like Scheme that has tail recursion, the language recognizes that it doesn't need the information on the intermediate function calls, and eliminates them. (This is how loops are internally implemented in Scheme!)

So isn't this optimization always a good thing? Well, not completely. In Perl, for instance, we have a caller function. This can be very useful for debugging. But in Scheme it would be impossible to implement because there is no information about calls that have been cleaned up already. (OK, so you can do the same with goto in Perl, but people don't use that very much so debugging information tends to be there when you want to create a stack backtrace.)

In reply to Re^2: Puzzled by Recursion. (comparing basic vs tail recursion) by tilly
in thread Puzzled by Recursion. by Anonymous Monk

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.