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.

- Recursive with stack usage and
`memoize`

- Recursive with tail call
- With
`reduce`

function - 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:

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