Iterating Over the Fibonacci Numbers

by Andrew Johnson

September 5, 2001 —

Consider the Fibonacci numbers (0,1,1,2,3,5,8,13,21,34,...), where the
next number is the sum of the previous two in the series. We could
create a recursive routine to calculate these:

#!/usr/bin/perl -w
use strict;

sub fib {
my $n = shift;
return $n if $n < 2;
fib($n-1) + fib($n-2);
}

for(0..9) {
print fib($_),"\n";
}
__END__

However, due to its recursive nature, the fib() routine must
recalculate earlier numbers in the series every time it is called. One
simple solution is to create a cache that stores numbers in the series,
and then have the function use those if they exist. This is called
Memoization and there is a Memoize module on CPAN (we discussed this
module back in May 2001). This technique is a trade off between using
more space (the cache) and gaining more speed.

If one only wishes to iterate through the series in order (perhaps with
breaks to do other processing), then another solution is to create an
iterator using a closure:

#!/usr/bin/perl -w
use strict;
sub gen_fib {
my($curr, $next) = (0,1);
return sub {
my $fib = $curr;
($curr, $next) = ($next, $curr + $next);
return $fib;
};
}

my $fib_stream1 = gen_fib();
my $fib_stream2 = gen_fib();

# print first 5 fibonacci numbers from stream 1
print "Stream One:";
for(1..5){
print $fib_stream1->(), ' ';
}
print "\n";

# print first 10 from stream 2
print "Stream Two:";
for (1..10) {
print $fib_stream2->(), ' ';
}
print "\n";

# print next 5 from stream 1
print "Stream One:";
for(1..5){
print $fib_stream1->(), ' ';
}
print "\n";
__END__

This technique offers some advantages. It only stores enough state to
calculate the next number (without recursion) rather than all the
previous numbers in the series as memoization does, and you can have
more than one independent iterator (or stream) in the same program.
However, this technique also has some disadvantages. It is only useful
in cases where you actually want to iterate through the series. It is
not useful for calculating the Nth Fibonacci number (which the
recursive solution could be used for).

You do not have to iterate over mathematical functions, you can iterate
over anything. It is possible to create an iterator that iterates over
N arrays in n-tuples (i.e., get the first item from each array, then
the second, etc...). With an array of array refs as a table, this is
analagous to iterating over the columns rather than the rows.

ITworld