Why is recursion so slow?

[Luis Zarrabeitia]

Quoting slix <notnorwegian at 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 says to
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 a long 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 with 0,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