A good introduction to recursion is Higher-Order Perl Chapter 1: Recursion and Callbacks. The walk-through starts simple with binary numbers, then moves on to directory traversal, the meat and potatoes of recursion :) A quick foray into html tree traversal (just like directory tree, trees are the meat and potatoes ) and it ends with Fibonacci in section 1.8 When Recursion Blows Up

Devel::TraceCalls shows the tree (book one or two nice pics)

#!/usr/bin/perl --
use strict; use warnings;
use Devel::TraceCalls { Subs => [qw/fib /]};
print fib(5);
sub fib {
  my $n = shift;
  if ($n < 2) { return $n }
  fib($n-2) + fib($n-1);
}
__END__
TRACE: main::fib( 5 )
TRACE: +-main::fib( 3 )
TRACE: | +-main::fib( 1 )
TRACE: | +-main::fib( 2 )
TRACE: | ! +-main::fib( 0 )
TRACE: | ! +-main::fib( 1 )
TRACE: +-main::fib( 4 )
TRACE: | +-main::fib( 2 )
TRACE: | ! +-main::fib( 0 )
TRACE: | ! +-main::fib( 1 )
TRACE: | +-main::fib( 3 )
TRACE: | ! +-main::fib( 1 )
TRACE: | ! +-main::fib( 2 )
TRACE: | ! | +-main::fib( 0 )
TRACE: | ! | +-main::fib( 1 )
5
[download]

If you made a directory mimicking fib-5 you can see the tree in your file browser

Or with tree

fib-5
|-- fib-3
|   |-- fib-1
|   `-- fib-2
|       |-- fib-0
|       `-- fib-1
`-- fib-4
    |-- fib-2
    |   |-- fib-0
    |   `-- fib-1
    `-- fib-3
        |-- fib-1
        `-- fib-2
            |-- fib-0
            `-- fib-1
[download]

Chapter 5: From Recursion to Iterators, deals with Eliminating Recursion from fib ( see fib-0, fib-1, fib-2 ... )

I understand the mathematical equations entirely... what I can't grasp is how Perl is handling the recursion.

Perhaps it is as simple as the math, but it just ain't 'clicking', hence my question.

I understand the mathematical equations entirely... what I can't grasp is how Perl is handling the recursion.

Perhaps it is as simple as the math, but it just ain't 'clicking', hence my question.

Um, yes, its exactly like the math. It didn't click for me either until I wrote it out by hand with a pencil.

#!/usr/bin/perl --
use strict; use warnings;
print fib(5);
sub fib {
  my( $n, $depth ) = @_;
  $depth ||= 0;
  print "(d $depth)", " " x $depth, " (n $n)\n";
  if ($n < 2) { return $n }
  fib($n-2, $depth + 1 ) + fib($n-1 , $depth + 1 );
}
__END__
(d 0) (n 5)
(d 1)  (n 3)
(d 2)   (n 1)
(d 2)   (n 2)
(d 3)    (n 0)
(d 3)    (n 1)
(d 1)  (n 4)
(d 2)   (n 2)
(d 3)    (n 0)
(d 3)    (n 1)
(d 2)   (n 3)
(d 3)    (n 1)
(d 3)    (n 2)
(d 4)     (n 0)
(d 4)     (n 1)
5
[download]