in reply to Fibonacci Numbers

2 things:
If you stick with the original form of your answer (a recurrance-based one), try Memoizing it, viz.: 
# Compute Fibonacci numbers, straight from Memoize docs
use Memoize;
memoize('fib');

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

my $foo = fib(24);

[download]
Such a strategy stores the results of previous iterations for later use, so you only have to calculate each result once. Once you do, it's stored (behind the scenes) in a hash which reconstructs it on demand. This makes things much faster.

But more importantly, I would offer this verson of an answer as a possible contender. It's a one-liner, but of a different style: 
sub fib{int(((((1+sqrt(5))/2)**$_[0])/sqrt(5))+.5)}

[download]
enjoy!



Code is (almost) always untested.
http://www.justicepoetic.net/

Replies are listed 'Best First'.
Re^2: Fibonacci Numbers
by crashtest (Curate) on Feb 10, 2005 at 07:29 UTC
    Sweet! The Binet Formula! This Mathworld entry shows how the Fibonacci sequence, the Binet Forms and the Golden Ratio fit together.

    For all the times the Fibonacci sequence comes up as an exercise in programming recursion, I've never seen it solved quite like that. Goes to show that TIMTOWTDI, as usual.
[reply]
Re^2: Fibonacci Numbers
by blazar (Canon) on Feb 10, 2005 at 08:23 UTC
    If you stick with the original form of your answer (a recurrance-based one), try Memoizing it, viz.:
    But the original form of his answer was not recursive: 
    sub fib{
($val0, $val1) =@_;
$sum= $val0 + $val1;
}

    [download]
[reply]
[d/l]
      Honourable friar, Am I wrong to think that recurrsion is utilized by passing the value of $sum as computed by sub fib back into sub fib? Otherwise, the binet formula is extremely cool. Thanks.
[reply]
        This is a recursive way to do it but it gets slow quickly for larger values unless you memoze it. 
        print "$_ : ", fibo($_), "\n" for 0..23;

sub fibo{
    my $n = shift;
    if ( $n == 0){ return 0;}
    elsif( $n == 1){ return 1;}
    else { return fibo($n-1) + fibo($n-2);}
}

        [download]
[reply]
[d/l]
        It is iterative. It is not recursive in that fib() does not call itself.

        FWIW I think that Binet's formula is cool too.

[reply]
[d/l]
Re^2: Fibonacci Numbers
by ihb (Deacon) on Feb 10, 2005 at 23:49 UTC

    Not that it matters much to me, but for the 71st number I get a round-off error using Binet's formula. 

    sub fib {int(((((1+sqrt(5))/2)**$_[0])/sqrt(5))+.5)}

sub fib2 {
    my ($n) = @_;

    my ($x, $y) = (1, 1);
    ($x, $y) = ($y, $x + $y)
        for 3 .. $n;

    return $y;
}

for (my $n = 1; 1; $n++) {
    my ($x, $y) = (fib($n), fib2($n));
    if ($x != $y) {
        print "$n: $x $y";
        last;
    }
}

__END__
71: 308061521170130 308061521170129

    [download]

    Regards,
    ihb

    See perltoc if you don't know which perldoc to read!

[reply]
[d/l]
      Try Math::BigFloat's rounding handling instead of the int(foo+.5) trick, and things should work out.



      Code is (almost) always untested.
      http://www.justicepoetic.net/
[reply]

In Section Seekers of Perl Wisdom