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