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))
    )
  )
)