How do I generate memoized recursive functions in Clojure?

(def fib (memoize (fn [x] (if (< x 2)
                              x
                              (+ (fib (- x 1))
                                 (fib (- x 2)))))))
(time (fib 35))

Here is the simplest solution:

(def fibo
  (memoize (fn [n]
             (if (< n 2)
               n
               (+ (fibo (dec n))
                  (fibo (dec (dec n))))))))

There is an interesting way to do it that does rely neither on rebinding nor the behavior of def. The main trick is to go around the limitations of recursion by passing a function as an argument to itself:

(defn make-fibo [y]
  (let
    [fib
      (fn [mem-fib x]
         (let [fib (fn [a] (mem-fib mem-fib a))]
           (if (<= x 2)
             y
             (+ (fib (- x 1)) (fib (- x 2))))))
     mem-fib (memoize fib)]

     (partial mem-fib mem-fib)))

Then:

> ((make-fibo 1) 50)
12586269025

What happens here:

• The fib recursive function got a new argument mem-fib. This will be the memoized version of fib itself, once it gets defined.
• The fib body is wrapped in a let form that redefines calls to fib so that they pass the mem-fib down to next levels of recursion.
• mem-fib is defined as memoized fib
• ... and will be passed by partial as the first argument to itself to start the above mechanism.

This trick is similar to the one used by the Y combinator to calculate function's fix point in absence of a built-in recursion mechanism.

Given that def "sees" the symbol being defined, there is little practical reason to go this way, except maybe for creating anonymous in-place recursive memoized functions.

This seems to work:

(defn make-fibo [y]
  (with-local-vars
      [fib (memoize
            (fn [x]
              (if (< x 2)
                y
                (+ (fib (- x 2)) (fib (dec x))))))]
    (.bindRoot fib @fib)
    @fib))

with-local-vars only provides thread-local bindings for the newly created Vars, which are popped once execution leaves the with-local-vars form; hence the need for .bindRoot.