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]