Fibonacci Numbers

I finally got a syntax highlighter installed, so as celebration I give you two methods for getting the Nth number in the Fibonacci sequence.

#!/usr/bin/perl -w

use strict;
use POSIX qw(floor);

# Array of found fib(n)
my @found;

# Counter for number of calculations
my $z = 0;

sub fib {
	# The Nth number.
	my $n = shift;
	
	# Check for end of recrusion.
	if($n <= 0)		{return 0;}
	elsif($n == 1)		{return 1;}
	
	# If we already found the fib for this number, just return it.
	elsif($found[$n])	{return $found[$n];}
	
	# If we didn't find it yet, look for it.
	else {
		# Put it in an array so we can find it later too.
		$found[$n] = fib($n-1) + fib($n-2);
		
		$z++;
		return $found[$n];
	}
}

my $x = 20; #floor(rand(100));
my $y = fib($x);
print "fib($x) = $y\nNumber of calculations: $z\n";

Note that I store the numbers that I find in $found to make the process much more efficient.

#!/usr/bin/perl -w

use strict;
use POSIX qw(floor);

# set the first two numbers
my @sequence = (0, 1);

# the position we want to find
my $find = 20;#floor(rand(100));

# Using a loop instead of recursion. Note: index 0 is the *second* fibonacci number.
for( my $i = 0; $i < ($find - 1); $i++ ) {
	# next position = current + previous
	$sequence[$i + 1] = $sequence[$i] + $sequence[$i - 1];
	
	# print the calculation
	print "[$i] ".$sequence[$i - 1]." + ".$sequence[$i]." = ".$sequence[$i + 1]."\n";
}

# finally, print the results
print "The Fibonacci number at position ".$find." is ".$sequence[$find - 1]."\n";