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: 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)
  • Re: Error C2040
    ... of when *not* to use recursion. ... calculate, by a straitlaced method, the number of Fibonacci ... checks to see whether the result already exists in the array. ... sum to set arraybefore returning that sum. ...
    (comp.lang.c)
  • Re: Software bugs arent inevitable
    ... > First of all, the recursive version of Fibonacci IS EXPONENTIAL in complexity, ... themselves part of a Fibonacci-like sequence. ... But it is a very common algorithm -- I have four or five textbooks at home ... > Such anti-advertizing of recursion says less about the recursion ...
    (comp.lang.python)