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

md fib-5
md fib-5\fib-3
md fib-5\fib-3\fib-1
md fib-5\fib-3\fib-2
md fib-5\fib-3\fib-2\fib-0
md fib-5\fib-3\fib-2\fib-1
md fib-5\fib-4
md fib-5\fib-4\fib-2
md fib-5\fib-4\fib-2\fib-0
md fib-5\fib-4\fib-2\fib-1
md fib-5\fib-4\fib-3
md fib-5\fib-4\fib-3\fib-1
md fib-5\fib-4\fib-3\fib-2
md fib-5\fib-4\fib-3\fib-2\fib-0
md fib-5\fib-4\fib-3\fib-2\fib-1
[download]

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