# 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(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

.

**Follow-Ups**:**Re: calculating fibonacci[was: encryption]***From:*Ben Bacarisse

**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

- 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):