Memoize in Clojure

2023-05-17

Memoization is the process of caching expensive calculations so that they can later be used to speed up a program.

An example of this in Clojure can be seen with an implementation of this fib function, which returns the nth Fibonacci number.

(defn fib [n]
  (cond
    (<= n 0) 0
    (= n 1) 1
    :else (+ (fib (- n 1)) (fib (- n 2)))))

We can see that it simply uses the recursive definition of the nth Fibonacci number. But this is actually pretty slow because the recursion is calculating the same values multiple times.

For example:

(time (fib 40)) ;=>"Elapsed time: 964.588292 msecs"
                ;=>102334155

A way to optimize this in terms of speed would be to create a memoized version of the fib function. This will speed it up, but also take up more memory during runtime.

(def fib-memoize
  (memoize
    #(cond
     (<= % 0) 0
     (= % 1) 1
     :else (+ (fib-memoize (- % 1)) (fib-memoize (- % 2))))))

Note that we can't just do (def fib-memoize (memoize fib)) because that will only memoize the top call of fib and none of the other recursive ones.

This memoization greatly increases the speed of the calculation:

(time (fib-memoize 40)) ;=>"Elapsed time: 0.352458 msecs"
                        ;=>102334155