Fibonacci in Clojure

Notes

number <- index
0 <- 1
1 <- 2
1 <- 3
2 <- 4
3 <- 5
5 <- 6
8 <- 7
13 <- 8
21 <- 9

                    (fib 5)
                    /   \
            (fib 4)     (fib 3)
            /    \        /   \
      (fib 3) (fib 2)  (fib 2) (fib 1)
      /    \
  (fib 2) (fib 1)

;; fibo.clj

(defn fib [index]
  (cond
    (= index 1) 0
    (= index 2) 1
    :else (+
          (fib (- index 1))
          (fib (- index 2)))))


(def memoize-fib (memoize fib))

(memoize-fib 10)

Timing fibonacci:

(time (fib 30))
(time (memoize-fib 30))

Classic Computer Science Problems in Python