Local memoized recursive functions

You probably know how to create a top-level memoized recursive function in Clojure, but how do you create a local one? By local, I mean defined with let or letfn.

For the lack of better example, consider a Clojure function that returns the n-th Fibonacci number. Here’s a top-level definition created with defn:

(defn fibo [n]
  (if (< n 2)
    n
    (+ (fibo (dec n)) (fibo (- n 2)))))

It’s a classic example of recursive function. However, the implementation above is not exactly efficient. If you run (fibo 50), it will take forever to finish.

There are two standards ways to make it fast: tail recursion and memoization. You can use clojure.core/memoize to create a memoized version of fibo:

(def fibo2
  (memoize
    (fn [n]
      (if (< n 2)
        n
        (+ (fibo2 (dec n)) (fibo2 (- n 2)))))))
        
(fibo2 20)  ; 6765
(fibo2 50)  ; 12586269025

This is fast enough for calculating the 50th Fibonacci number.

fibo2 is defined on the top level, but how do you create a locally-bound version of it? It seems like it shouldn’t be too hard. Here’s the non-memoized version created with let:

(let [fibo (fn fibo [n]
             (if (< n 2)
               n
               (+ (fibo (dec n)) (fibo (- n 2)))))]
  (fibo 20))

Note that we had to name the function twice: first in the let form and second time inside fn. This is because the binding created by let is not visible inside fn. With letfn, only one name is enough:

(letfn [(fibo [n]
          (if (< n 2)
            n
            (+ (fibo (dec n)) (fibo (- n 2)))))]
  (fibo 20))

Exercise: If you want, try to define a memoized version of fibo inside let yourself. Try calling it with large n to check that it works correctly.

Here are a couple of nice pictures so that you don’t accidentally scroll to the answer before you’re ready. If you don’t feel like attempting the exercise, that’s okay too.

We can’t use memoize with leftn, so let’s continue with let. Here’s a naïve attempt:

(let [fibo (memoize (fn fibo [n]
                      (if (< n 2)
                        n
                        (+ (fibo (dec n)) (fibo (- n 2))))))]
  (fibo 20))

If you try this with (fibo 50), you’ll notice that it does not work as intended. This is because inside the fn, fibo refers to the fn itself and not to the memoize-wrapped version. If you called (fibo 50) twice in a row, the second time would be fast since the final result of the calculation does get memoized.

There are a bunch of solutions on StackOverflow. For example, the answer by Michał Marczyk can be adopted:

(let [fibo
      (with-local-vars
        [fibo (memoize (fn [n]
                         (if (< n 2)
                           n
                           (+ (fibo (dec n)) (fibo (- n 2))))))]
        (.bindRoot fibo @fibo)
        @fibo)]
  (fibo 50))

However, this code probably makes you go hmmm. Calling Var methods via Java interop does not feel like very Clojure-like to me. I want to offer an alternative, more functional solution.

The function can’t refer to the memoized version of itself from the inside, but we can pass it in from the outside as a parameter. Let’s first try it without memoization:

(let [fibo (fn [rec n]
             (if (< n 2)
               n
               (+ (rec rec (dec n)) (rec rec (- n 2)))))]
  (fibo fibo 40))

The first parameter of fibo is the function itself. It looks a bit odd, but it works! We can, once again, clean it up by using a fixed-point combinator. It allows us to wrap fibo so that it receives the wrapped version of itself as the first argument.

(defn fix [f] (fn g [& args] (apply f g args)))

(let [fibo (fn [fibo n]
             (if (< n 2)
               n
               (+ (fibo (dec n)) (fibo (- n 2)))))
      fibo2 (fix fibo)]
  (fibo2 20))

Now the function definition looks pretty normal. fibo takes “itself” as the first parameter, but it’s not very different from (fn fibo [n] ...). Let’s try to memoize it:

(let [fibo (fn [fibo n]
             (if (< n 2)
               n
               (+ (fibo (dec n)) (fibo (- n 2)))))
      fibo2 (fix (memoize fibo))]
  (fibo2 50))

It works!

I’m always delighted to find use cases for fixed-point combinators. Writing a nice macro to wrap this up is left as an exercise for the reader.