Next | The Perl Hardware Store | DC.pm Version | 31 |
Solution: Caching
@fib = (0, 1); sub fib { my ($n) = @_; return $fib[$n] if defined $fib[$n]; return $fib[$n] = fib($n-1) + fib($n-2); }
fib(20) computes fib(18) and fib(19)
fib(19) goes to compute fib(18)
But it is already in $fib[18]
Function is now very fast
Almost as fast as a pure iterative version
Unlike the iterative version, this version required no ingenuity
Next | Copyright © 2003 M. J. Dominus |