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