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.