In Fibonacci Sequence – Part 1, we saw the recursive versions of JavaScript and Perl to calculate the Fibonacci sequences.

The main drawback of them is performance. (To test, try calculating `fib(5)`

and `fib(50)`

.)

The formula is `fib(n) = fib(n - 1) + fib(n - 2)`

Which means that while calculating `fib(n - 1)`

, we already calculate `fib(n - 2)`

But, as it is not stored anywhere, we are again calculating `fib(n - 2)`

(You might think of some temporary variable to store this value. But, hold on.)

To calculate `fib(n - 2)`

, we require `fib(n - 3)`

and `fib(n - 4)`

.

We already calculated these values but didn’t store anywhere.

This goes on until `fib(3)`

(We know what `fib(2)`

and `fib(1)`

are, right?).

Hence what we need is a list of temporary variables or just an array.

function fib(n) { var t; // variable to hold the temporary array if(n == 1) t = [0]; // we know the first two terms else if(n == 2) t = [0, 1]; // i.e. for n = 1 or n = 2 else if(n >= 3) { t = fib (n - 1); // get the previous terms (array and recursion) // now calculate the nth term t[t.length] = t[t.length - 2] + t[t.length - 1]; } return t; } alert(fib(10));

The above JavaScript function gives the list of fibonacci numbers until the nth term.

Now, let us see the beautiful Perl version

use 5.10.0; # required for the use of given/when construct sub fib { my @t; given (pop) { # Get the argument and inspect it when (1) { @t = (0) } # If the arg is 1 then when (2) { @t = (0, 1) } # arg 2 when ($_ >= 3) { # The default variable @t = fib ($_ - 1); # get the previous terms $t[@t] = $t[@t - 2] + $t[@t - 1]; # nth term } } return @t; } my @fib = fib($ARGV[0]); print "@fib\n";

That’s the thing.

Here, we use an array of temporary variables to optimize.

They help us to hold the results of previous calculations.

They help us in reducing the consumptions of CPU cycles.

Please check out the `Memoize`

module on CPAN.

It is not about how fast the hardware do the computations.

It is still in the hands of the programmers to deliver the quality software.

*Food for thought:* What if we are trying to memorize everything and every other thing?

I have some more things to talk about Fibonnacci Sequence.