Quoting slix <no**********@yahoo.se>:

Recursion is awesome for writing some functions, like searching trees

etc but wow how can it be THAT much slower for computing fibonacci-

numbers?

The problem is not with 'recursion' itself, but with the algorithm:

def fibr(nbr):

if nbr 1:

return fibr(nbr-1) + fibr(nbr-2)

if nbr == 1:

return 1

if nbr == 0:

return 0

If you trace, say, fibr(5), you'll find that your code needs to compute fibr(4)

and fibr(3), and to compute fibr(4), it needs to compute fibr(3) and fibr(2). As

you can see, fibr(3), and it whole subtree, is computed twice. That is enough to

make it an exponential algorithm, and thus, untractable. Luckily, the iterative

form is pretty readable and efficient. If you must insist on recursion (say,

perhaps the problem you are solving cannot be solved iteratively with ease), I'd

suggest you to take a look at 'dynamic programming', or (easier but not

necesarily better), the 'memoize' disgn pattern.

is the recursive definition counting fib 1 to fib x-1 for every x?

Yes - that's what the algorithm says. (Well, actually, the algorithm saysto

count more than once, hence the exponential behaviour). The memoize patter could

help in this case.

is

that what lazy evaluation in functional languages avoids thus making

recursive versions much faster?

Not exactly... Functional languages are (or should be) optimized for recursion,

but if the algorithm you write is still exponential, it will still take along time.

is recursive fibonacci in haskell as fast as an imperative solution in

a procedural language?

[...]

i found a version in Clojure that is superfast:

I've seen the haskell implementation (quite impressive). I don't know Clojure

(is it a dialect of Lisp?), but that code seems similar to the haskell one. If

you look closely, there is no recursion on that code (no function calls).The

haskell code works by defining a list "fib" as "the list that starts with0,1,

and from there, each element is the sum of the element on 'fib' plus the element

on 'tail fib'). The lazy evaluation there means that you can define a list based

on itself, but there is no recursive function call.

Cheers,

(I'm sleepy... I hope I made some sense)

--

Luis Zarrabeitia

Facultad de Matemática y Computación, UH

http://profesores.matcom.uh.cu/~kyrie