Thank you for posting working code. It is a clear example. I tweaked a little. Not comprehensive but indentation, as shown in previous examples from other monks, in particular is good for recursion examples, I think.

sub foo {
    # 4 spaces or tab is standard. Why be different here?
    # Even this spotty arg check is better than none.
    my $nesting_level = shift || die "Nesting level needed!";
    # Indentation is a great way to visualize recursion.
    my $indent = "    " x ( $nesting_level - 1 );
    print $indent, "Hello from level $nesting_level!\n";
    # It's Perl, why not postfix?
    foo($nesting_level+1) if $nesting_level < 3;
    print $indent, "Goodbye from level $nesting_level!\n";
}
[download]

Hello from level 1!
    Hello from level 2!
        Hello from level 3!
        Goodbye from level 3!
    Goodbye from level 2!
Goodbye from level 1!
[download]