Part of the beauty of Haskell is that it allows you to simply
write recursive functions. But part of the problem with
recursive functions is that they tend to have absolutely
horrible big-O run times. The usual solution to this problem is
to use what’s known as memoization, which is memorization
without the ‘r’, since programmers have to have special names
for everything. Memoization is usually implemented as an
associative array (or a plain array in the common case where the
function takes a single non-negative integer as an argument);
the function attempts to look up the return value for its
arguments in an associative array. If it finds it, it can return
without doing expensive computation; if it doesn’t, then it
performs the computation, stores the result in its array, and
then returns. In Python, a memoized Fibonacci function might be
written as follows: if (n < 2): return n if n not in fib_cache:
fib_cache[n] = fib(n-1) + fib(n-2) The speed savings gained by
this are enormous; on my test machine, fib(35