# Coding a Fibonacci sequence in Clojure

After watching what other Clojure hackers have been doing for a few days in Advent of Code I’ve decided to try and do a few experiments with a basic Fibonacci generator.

First I did a simple recursive solution:

```
(defn fibo-rec [n]
(if (<= n 2)
1
(+ (fibo-rec (- n 1)) (fibo-rec (- n 2)))
)
)
```

The obvious problem with this solution is that it recomputes already computed solutions.

I’ve seen a lot of people use the ->> macro. Here’s a reimplementation using the macro and a loop:

```
(defn fibo-op [n]
(if (<= n 2)
1
(loop [n-2 1 n-1 1 ct n]
(if (<= ct 2)
n-1
(recur n-1 (->> [n-2 n-1] (apply +)) (dec ct))
)
)
)
)
```

The part `(->> [n-2 n-1] (apply +))`

works like a pipeline where each expression gets fed into next expression.
End result can also be written as `(apply + [n-2 n-1])`

. `loop`

does feel a bit non-idiomatic in the functional world
and I tend to avoid it if I can.

I’ve also found a use for a technique called memoization.
Memoization works like a cache for function results. The first time a function is called with specific arguments will execute as normal but every other time it will
return a cached result from first invocation. This may work well with a dynamic programming style solution instead of using a table.

Here’s a reimplementation of sequence calculation using memoization:

```
(def fibo-mem
(memoize
(fn [n]
(if (<= n 2) 1 (+ (fibo-mem (- n 2)) (fibo-mem (- n 1))))
)
)
)
```

Every call to `fibo-mem`

is only executed **once** instead of being continuously recomputed as is the case in `fibo-rec`

.

To finish here’s how to call all three variants:

```
defn -main
"Operator fun."
[& args]
(loop [i 1]
(when (< i 10)
(println "Fibonacci sequence(recursive:" (fibo-rec i))
(println "Fibonacci sequence(->>):" (fibo-op i))
(println "Fibonacci sequence(memoize):" (fibo-mem i))
(recur (->> i inc))
)
)
)
```