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
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 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
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
(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 [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
fn. This is because the binding created by
let is not visible
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
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
leftn, so let’s continue with
let. Here’s a
(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
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
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))
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.