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

.



Relevant Pages

  • Re: calculating fibonacci[was: encryption]
    ... int fib ... Recursion! ... solution only calculates fib, without calculating any others. ...
    (comp.programming)
  • Re: calculating fibonacci[was: encryption]
    ... Fibonacci is a rather unfortunate case for recursion. ... solution only calculates fib, without calculating any others. ...
    (comp.programming)
  • Re: recursion using threads
    ... Richard Damon writes: ... Why would you rule out recursion for calculating large Fibonacci ... The issue is that a naive recursion will do enormously too much work. ...
    (comp.lang.c)
  • Re: recursion using threads
    ... Why would you rule out recursion for calculating large Fibonacci ... a clever recursive solution, when the non-recursive solution is so ...
    (comp.lang.c)
  • Re: Software bugs arent inevitable
    ... It relies on the observation that calculation of the fibonacci ... def expo: ... increasing the recursion depth, even though the expo function is ...
    (comp.lang.python)