Re: Puzzled by Recursion. (comparing basic vs tail recursion)

Others have explained the concept of recursion, but I'd like to mention something about tail recursion, which is slightly different from what you have listed above. (Let me preface this by saying I'm not an expert at algorithms, so I might not be as precise with the wording as I should be.)

In your original sub, the first call to the sub can't return a value until two more calls are made (for fibonacci($pop-1) + fibonacci($pop-2)), and each of those subs can't return until two more calls are made, etc. If $pop is large, the stack will fill up with many sub calls waiting for return values. In addition, a lot of extra work will be done because fibonacci(n)(and subsequently fibonacci(n-1), fibonacci(n-2), etc) will be called repetitively for every value of $pop greater than or equal to n.

In tail recursion, extra variables are used to retain intermediate values, so the subs on the stack are kept to a minimum and there isn't any wasted computation.

To illustrate the difference, here is a comparison between the number of sub calls using TedPride's correction of your original algorithm, and a tail recursive algorithm (which I'm sure could be optimized). The code:

use strict;
use warnings;

my $counter;

foreach my $num ( 1 .. 5, 10, 15, 25 )
{
    $counter = 0;

    print "\n$num by orig";
    my $result = fibonacci( $num );
    print " = $result ($counter calls to sub)\n";

    $counter = 0;

    print "$num by tail";
    $result = fib_tail( $num );
    print " = $result ($counter calls to sub)\n";
}

sub fibonacci
{
    $counter++;

    return 1 if $_[0] < 3;

    return fibonacci( $_[0] - 1 ) + fibonacci( $_[0] - 2 );
}

sub fib_tail
{
    my $max_num = shift || 0;
    my $cur_num = shift || 0;
    my $tot_2   = shift || 0;
    my $tot_1   = shift || 0;

    $counter++;

    if   ( $cur_num == 1 ){ $tot_1 = 1; }
    elsif( $cur_num == 2 ){ $tot_2 = 0; }

    return $tot_2 + $tot_1 if( $cur_num == $max_num );

    return fib_tail( $max_num, $cur_num + 1, $tot_1, $tot_2 + $tot_1 )
+;
}
[download]

Here is the output. Notice the dramatic difference in the number of sub calls required by the non-tail-recursive algorithm when $pop gets large.

1 by orig = 1 (1 calls to sub)
1 by tail = 1 (2 calls to sub)

2 by orig = 1 (1 calls to sub)
2 by tail = 1 (3 calls to sub)

3 by orig = 2 (3 calls to sub)
3 by tail = 2 (4 calls to sub)

4 by orig = 3 (5 calls to sub)
4 by tail = 3 (5 calls to sub)

5 by orig = 5 (9 calls to sub)
5 by tail = 5 (6 calls to sub)

10 by orig = 55 (109 calls to sub)
10 by tail = 55 (11 calls to sub)

15 by orig = 610 (1219 calls to sub)
15 by tail = 610 (16 calls to sub)

25 by orig = 75025 (150049 calls to sub)
25 by tail = 75025 (26 calls to sub)
[download]

The difference between basic recursion and tail recursion is barely noticable at small values, but the extra time it takes to code a tail-recursive algorithm pays off quickly when the input values get even a little larger. Try using an input value of 50 and you'll see what I mean.

HTH

Update:

The code I gave above was translated from an example in "Mastering Algorithms with C" (O'Reilly), so it was not specifically a perl example. tilly was kind enough to clarify his reply to this post for me in the cb. The words that follow are more his than mine, but it helped me understand things better so I decided to add it to this node.

Tail recursion refers to automatically eliminating unnecessary call-frames. It is possible in Perl, but not automatically. You have to use goto &name; to do it, and in many versions of Perl it will leak a bit of memory (defeating the purpose).

Some other optimization may also have been given that name. But what most people that I've heard talk about it mean is the idea that is built into Scheme, and the ability to do that is language specific.

Thank you for the clarification, tilly!

Comment on Re: Puzzled by Recursion. (comparing basic vs tail recursion) Select or Download Code

Replies are listed 'Best First'.
Re^2: Puzzled by Recursion. by polettix (Vicar) on Apr 01, 2005 at 11:29 UTC
This is also the perfect playground for Memoize, because it will handle intermediate calls caching allowing you to concentrate into the main stuff. Fun is that the example for the Memoize module actually deals with the Fibonacci sequence! Flavio (perl -e "print(scalar(reverse('ti.xittelop@oivalf')))") Don't fool yourself.	[reply]
Re^2: Puzzled by Recursion. (comparing basic vs tail recursion) by tilly (Archbishop) on Jun 10, 2005 at 02:40 UTC
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.)	[reply] [d/l]