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.

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.

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.)

The function could be more simply (and correctly, since the function specified didn't give the right values) written as:

sub fibonacci {
    return 1 if $_[0] < 3;
    fibonacci($_[0]-1) + fibonacci($_[0]-2);
}
[download]

sub fibonacci {
    $_[0] < 3 ? 1 : fibonacci($_[0]-1) + fibonacci($_[0]-2);
}
[download]

1 1 2 3 5 8 13 etc.

Let's say you call the function with 4:

(4) Is 4 < 3? No. Return (4-1) + (4-2).
(4-1) Is 3 < 3? No. Return (3-1) + (3-2).
(3-1) Is 2 < 3? Yes. Returning 1.
(3-2) is 1 < 3? Yes. Returning 1.
(4-1) Returning 1 + 1.
(4-2) Is 2 < 3? Yes. Returning 1.
(4) Returning 2 + 1.
Answer returned is 3, which is the 4th number in the sequence.

See, every number in the sequence is built off the previous two values, each of which is built off the two values previous to it, and so on - all the way back to the first and second values (1 and 2 are < 3), which are 1. If the value passed to the function is 1 or 2, it knows to return 1; otherwise it calls itself twice to determine the previous two numbers in the sequence.

For me, the thing in code like this that still makes me look at it twice, is the implicit return. The result of the last expression evaluated in a sub is used as the return value if there's no explicit return.

I'm not looking to start yet another war here between people who like explicit returns and people who don't. Just wanted to point it out in case that's what the OP found confusing about the else clause, since noone seems to have mentioned it yet.