#!/usr/bin/perl -w


my %cache;

sub fib {
	my $x = shift;
	
	if ( $x == 0 or $x == 1 ) {
		return 1;
	} else {
		if ( defined($cache{$x}) ) {
			return $cache{$x};
		} else {
			return ( $cache{$x} = fib ($x - 1) + fib ($x - 2));
		}
	}
}


foreach (1..30) {
	print "$_: " . fib($_) . "\n";
}