# Local memoized recursive functions

## 2020-09-20

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.

Comments or questions? Send me an e-mail.