Re: calculating fibonacci[was: encryption]
 From: "Bartc" <bc@xxxxxxxxxx>
 Date: Sun, 14 Dec 2008 11:46:01 GMT
"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(n1) + fib(n2);
}
[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_{n1} exactly once to get fib(n).
The recursive solution above calculates fib(0) F_{n1} 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
.
 FollowUps:
 Re: calculating fibonacci[was: encryption]
 From: Ben Bacarisse
 Re: calculating fibonacci[was: encryption]
 References:
 encryption
 From: Bill Cunningham
 Re:calculating fibonacci[was: encryption]
 From: Bill Cunningham
 Re: Re:calculating fibonacci[was: encryption]
 From: Bill Cunningham
 Re: Re:calculating fibonacci[was: encryption]
 From: Richard Heathfield
 Re: Re:calculating fibonacci[was: encryption]
 From: Bill Cunningham
 Re: calculating fibonacci[was: encryption]
 From: Patricia Shanahan
 Re: calculating fibonacci[was: encryption]
 From: Ben Bacarisse
 encryption
 Prev by Date: Re: Why PHP is so succesfull?
 Next by Date: Re: calculating fibonacci[was: encryption]
 Previous by thread: Re: calculating fibonacci[was: encryption]
 Next by thread: Re: calculating fibonacci[was: encryption]
 Index(es):
Relevant Pages
