Why is recursion so slow?
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