Re: calculating fibonacci[was: encryption]



"Ben Bacarisse" <ben.usenet@xxxxxxxxx> wrote in message news:87fxkrk39u.fsf@xxxxxxxxxxxx
Patricia Shanahan <pats@xxxxxxx> writes:

Bill Cunningham wrote:
Osmium said:

[snip]

int fib(int n)
{
if(n==0)
return 0;
else if(n==1)
return 1;
else
return fib(n-1) + fib(n-2);
}

[snip]

Recursion! This is a good example right?

Fibonacci is a rather unfortunate case for recursion. A closed form
solution only calculates fib(n), without calculating any others. An
iterative solution calculates each Fibonacci number from F_0 through
F_{n-1} exactly once to get fib(n).

The recursive solution above calculates fib(0) F_{n-1} times to get
fib(n). For example, fib(0) is called 64,245,986 times in calculating
fib(40). At least on my laptop, it slows appreciably as n increases.

Of course not all recursive forms suffer this problem. My favourite
is this one in Haskell:

fib = 1 : 1 : map (uncurry (+)) (zip fib (tail fib))

The result is a list so you can get the 1000th Fibonacci number by
evaluating fib !! 1000. It is surprisingly fast.

With the downside that some of us can't make head or tail of it. What is it in English?

--
Bartc

.