Why is recursion so slow?

Nick Craig-Wood nick at craig-wood.com
Tue Jul 1 22:46:50 CEST 2008

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


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

More information about the Python-list mailing list