From: Daniel Martin <martin@...>
Date: 2006-07-13T22:06:00+09:00
Subject: Re: Recursion and Ruby

"Erik Veenstra" <erikveen@gmail.com> writes:

> You could use "case" as well (see version 2). It's faster.
> Using an ordinary if..else (without the elsif part) is faster
> (see version 3). And version 4 is once again faster.
>
> 4 is faster than 3 is faster than 2 is faster than 1...

All of these suffer from the problem that they make approximately fib(n)
function calls to compute fib(n).  Why not remember the value of
fib(n) the ruby way, with a Hash that computes it naturally?

$fib = Hash.new{|h,k| h[k] = h[k-2] + h[k-1]}
$fib[0] = 0
$fib[1] = 1

def fib(n)
  $fib[n]
end

This will be faster, and O(n), rather than O(fib(n)).  Also note that
the base cases of 0 and 1 are handled simply and declaratively without
messing up the main body of the code.

(Of course, now someone will respond with one of the O(log(n))
algorithms for computing fib(n))