fibonacci_in_lisp.clj

;;;; cf. http://riktor.hatenablog.com/entry/2012/07/20/224806

(defn fib [n]
  (if (or (= n 0) (= n 1))
    1
    (+ (fib (- n 1))
       (fib (- n 2)))))

(let [memo (atom {})]
  (defn fib-memoized [n]
    (if-let [m (get @memo n)]
      m
      (if (or (= n 0) (= n 1))
        1
        (let [m (+ (fib-memoized (- n 1))
                   (fib-memoized (- n 2)))]
          (swap! memo assoc n m)
          m)))))

(defn fib-loop [n]
  (loop [i n
         a 1
         b 0]
    (if (zero? i)
      a
      (recur (dec i)
             (+ a b)
             a))))