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 ) +; }
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)
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).Thank you for the clarification, tilly!
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.
In reply to Re: Puzzled by Recursion. (comparing basic vs tail recursion)
by bobf
in thread Puzzled by Recursion.
by Anonymous Monk
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |