Why is recursion so slow?

[Nick Craig-Wood]

Luis Zarrabeitia <kyrie at uh.cu> wrote:
> > 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.

Actually I think functional language are likely to perform
memoization.  By definition any function in a functional language will
always produce the same result if given the same arguments, so you can
memoize any function.

See here for a python memoize which makes the recursive algorithm run
fast...

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52201

-- 
Nick Craig-Wood <nick at craig-wood.com> -- http://www.craig-wood.com/nick