Four Ways of fib(n) with Clojure
Jan 17, 2017
3 minutes read

Calculation of nth Fibonacci number is one of the common example of introduction to programming. Here I wanted combine this example with some Clojure utilities in four ways.

  1. Recursive with stack usage and memoize
  2. Recursive with tail call
  3. With reduce function
  4. Imperative way with refs

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)

1. Recursive with stack usage and memoize

This example isn’t the ideal way but it’s important to understand how recursion works. Clojure has no tail recursion optimization by default. This example causes stack overflow error. memoize is a useful function to speed up when we’re sure the result of the function is always same and there is no need to call once more for side effects.

(defn fib [n]
  (if (> n 1)  ; if n=0 or n=1 return n
    (+ (fib (dec n)) (fib (- n 2)))
    n))

(time (fib 36))
;"Elapsed time: 3234.847424 msecs"
;= 14930352

(def fib-m
  (memoize
   (fn [n]
     (if (> n 1)
       (+ (fib-m (dec n)) (fib-m (- n 2)))
       n))))

(time (fib-m 36))
;"Elapsed time: 0.480431 msecs"
;= 14930352

(fib-m 10000)
;StackOverflowError   clojure.lang.Numbers.gt (Numbers.java:3864)

2. Recursive with tail call

Clojure offers recur for tail recursions. It calls the nearest loop or the function itself.

(defn fib-recursive [n]
  (if (> n 1)      ; if n=0 or n=1 return n
    (loop [x 1 f0 0 f1 1]
      (if (< x n)  ; if it reaches to n, return f1
        (recur (inc x) f1 (+ f0 f1))
        f1))
    n))

(time (fib-recursive 36))
;"Elapsed time: 0.073619 msecs"
;= 14930352

(time (fib-recursive 100))
;ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1501)

Oh we received an number overflow error. What is the problem? Clojure use java.lang.Long as the default precision type and we reached the maximum possible value. There are two options in this condition:

  1. Using clojure.lang.BigInt with (bigint x) or adding N to end of the number 123N. This will be expensive if we usually stay in Long range.
  2. Using +' operator. It automatically uses clojure.lang.BigInt if necessary when the overflow occurs.

Aritmetic operations have more best practices, it’ll be too much to try handling all of them here.

(+ 1 Long/MAX_VALUE)
;ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1501)

(type (+' 1 Long/MAX_VALUE))
;clojure.lang.BigInt

(type (+ 1N Long/MAX_VALUE))
;clojure.lang.BigInt

(defn fib-recursive [n]
  (if (> n 1)      ; if n=0 or n=1 return n
    (loop [x 1 f0 0 f1 1]
      (if (< x n)  ; if it reaches to n, return f1
        (recur (inc x) f1 (+' f0 f1)) ; long to bingint if necessary
        f1))
    n))

(fib-recursive 100000) ; pretty fast and no overflows
;=2597....75N

3. With reduce function

We just need to accumulate the numbers with the previous one. We can do it with reduce.

(defn fib-reduce [n]
  (if (> n 1) ; if n=0 or n=1 return n
    (first (reduce (fn [coll _]
                     [(+' (first coll) (second coll)) ; save total and the previous
                      (first coll)])                  ; in a vector
                   [1 0] ; initial values
                   (range 1 n)))
    n))

(fib-reduce 100000)
;=2597....75N

4. Imperative way with refs

Probably this is not the best code as an example but it gives an idea.

(defn fib-imperative [n]
  (let [x (atom n)
        fib0 (ref 0)
        fib1 (ref 1)
        fibt (ref 1)]
    (while (> @x 1)
      (do (dosync (ref-set fibt @fib1)
                  (alter fib1 #(+' % @fib0))
                  (ref-set fib0 @fibt))
          (swap! x dec)))
    @fib1))

(fib-imperative 100000)
;=2597....75N

A mini benchmark of these functions. fib-imperative looks really slow.

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

(map (fn [f]
       (reduce + (for [x (range 30)]
                   (function-time f 100000))))
     [fib-recursive fib-reduce fib-swap])
;(10.650267569 11.351116001000001 39.083980229000005)

In conclusion, fib-recursive seems the most nature and the fastest in four. Of course there are more ways like Binet Formula to calculate Fibonacci numbers, but here the goals was practicing Clojure.


Back to posts


comments powered by Disqus