;; the plain recursive definition, slow on purpose
(defn fib [n]
  (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))

;; memoize wraps any function into a caching one
(def mem-fib (memoize fib))

(defn timed [f x]
  (let [start (System/nanoTime)
        r (f x)]
    [r (quot (- (System/nanoTime) start) 1000000)]))

(doseq [i [1 2]]
  (let [[value msecs] (timed mem-fib 30)]
    (println (str i ": fib30 is " value ", msecs is " msecs))))
;; prints:
;; 1: fib30 is 832040, msecs is 193
;; 2: fib30 is 832040, msecs is 0