Fibonacci sequence with Clojure
Jan 19, 2017
3 minutes read

Fib(n) is calculated at this post. Another common example is generating the sequence. Here we do it in 4 ways:

  1. Recursive way
  2. With iterate
  3. With lazy-cat
  4. With lazy-seq

“Out of memory” errors depend on the JVM settings and the physical memory. The fibonacci serie with 1,000,000 items cause error at my computer but 100,000 items don’t cause. Please change these factors according to your environment. It’s important to understand how lazy sequences work.

fib(1) = 0
fib(2) = 0 1
fib(3) = 0 1 1
fib(4) = 0 1 1 2

1. Recursive way

The first solution coming to mind might be this one. Add the sum of last two numbers to the vector. conj, pop, peek are the fastest ways to manipulate collections.

(defn fib-seq [n]
 (if (> n 1) ; fib(1) is [0]
   (loop [x (- n 2)
          v [0 1]]
     (if (> x 0)
       (recur (dec x) (conj v (+ (peek v) (peek (pop v)))))
       v))
  [0]))

(fib-seq 15)
;=[0 1 1 2 3 5 8 13 21 34 55 89 144 233 377]

(defn function-time-sec [f x]
  (let [starttime (System/nanoTime)]
    (f x)
    (/ (- (System/nanoTime) starttime) 1e9)))

(function-time-sec fib-seq 100000)
;=0.497667624

(function-time-sec fib-seq 1000000)
;OutOfMemoryError Java heap space  java.math.BigInteger.add (BigInteger.java:1315)
;This is okay because the vector and numbers are really big

2. With iterate

This is not the ideal solution because it generates temporary vectors but it’s a good example to show how lazy sequences work.

(defn fib-iterate [m]
  (->> (iterate (fn [[x y]] [y (+' x y)]) [0 1])
       (take m)
       (map first)))

(function-time-sec fib-iterate 100000)
;=5.84E-6

5.84E-6 is very fast! This is impossible. The reason is iterate, take and map returns lazy sequences. The sequence didn’t realize because our code didn’t attempt to access any item of it. Here we realize the sequence.

(let [starttime (System/nanoTime)]
  (doall (fib-iterate 100000))
  (/ (- (System/nanoTime) starttime) 1e9))
;=0.516226539

(let [starttime (System/nanoTime)]
  (doall (fib-iterate 1000000))
  (/ (- (System/nanoTime) starttime) 1e9))
;OutOfMemoryError Java heap space
;We can't realize all items in the list, same problem with the first example

Now it’s okay but there are more ways to generate lazy sequences as seen below. Also we have another problem here, what if we want to get the 1.000.000th element of the sequence? Will it cause a memory error too? No, because we use lazy sequence and the unused elements will be garbage collected.

(let [m (fib-iterate 1000000)]
  (last m))
;= 12071...

(let [m (fib-iterate 1000000)]
  (+ (first m) (last m)))
;= 12071...

(let [m (fib-iterate 1000000)]
  (+ (last m) (first m)))
;OutOfMemoryError Java heap space
;; Head retention!

The last example causes head retention.

3. With lazy-cat

This example is from the book Professional Clojure. It generates a lazy sequence with lazy-cat. A very concise solution but it causes head retention too. It’s possible to improve it like the below example.

(def fib-lazy-cat
  (lazy-cat [0 1] (map +' (rest fib-lazy-cat) fib-lazy-cat)))

(last (take 1000000 fib-lazy-cat))
;Exception in thread "nREPL-worker-1" java.lang.OutOfMemoryError: GC overhead limit exceeded

4. With lazy-seq

This is from ClojureDocs.org. It generates fib sequence without head retention. This is the ideal way of generating lazy sequences.

(defn fib-lazy-seq
  ([] (fib 0 1))
  ([a b] (lazy-seq (cons a (fib-lazy-seq b (+' a b))))))

(last (take 1000000 (fib-lazy-seq)))
;= 12071...

Back to posts


comments powered by Disqus