my @fib4_cache;
sub fib4 {
    my $n = shift;
    return $fib4_cache[$n] //= do {
        $n < 2 ? $n : fib4($n-1) + fib4($n-2)
    };
}
__END__
C:\test>memofib.pl
          Rate     fib1     fib2     fib3     fib4
fib1    88.7/s       --    -100%    -100%    -100%
fib2  219835/s  247838%       --     -89%     -91%
fib3 2073455/s 2338415%     843%       --     -19%
fib4 2551114/s 2877136%    1060%      23%       --


##</code><code>##


cmpthese(-1, {
    fib1 => q{ fib1 20 },
    fib2 => q{ fib2 20 },
    fib3 => q{ fib3 20 },
    fib4 => q{ fib4 20 },
});


__END__
C:\test>memofib.pl
          Rate     fib1     fib2     fib3     fib4
fib1    87.4/s       --    -100%    -100%    -100%
fib2  223254/s  255377%       --     -89%     -91%
fib3 2071504/s 2370384%     828%       --     -20%
fib4 2579867/s 2952119%    1056%      25%       --

##</code><code>##

my @fib5_cache;
sub fib5 {
    my $n = shift;
    return $fib5_cache[ $n ] //= do {
        $n < 2 ? $n
        : ( $fib5_cache[ $n-1 ] //= fib5($n-1) )
        + ( $fib5_cache[ $n-2 ] //= fib5($n-2) ) ## corrected; thanks to moriitz
    };
}

__END__
C:\test>memofib.pl
          Rate     fib1     fib2     fib3     fib4     fib5
fib1    89.0/s       --    -100%    -100%    -100%    -100%
fib2  218452/s  245352%       --     -89%     -91%     -91%
fib3 2022174/s 2272005%     826%       --     -18%     -20%
fib4 2478824/s 2785096%    1035%      23%       --      -2%
fib5 2537045/s 2850512%    1061%      25%       2%       --