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 );
}

##</code><code>##

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)