Memoized Y-Combinator

y.clj

;; Y-combinator
(defn Y [f] ((fn [x] (f (fn [y] ((x x) y))))
             (fn [x] (f (fn [y] ((x x) y))))))


;; Y-combinator memoized
(defn Y [f]
  (let [c (atom {})
        fp-gen (fn [x] (f (fn [y]
                            (or (@c y)
                                (let [v ((x x) y)]
                                  (swap! c assoc y v)
                                  v)))))]
    (fp-gen fp-gen)))

(def fib (Y (fn [fib]
              (fn [n] (condp = n
                       0 0
                       1 1
                       (+ (fib (- n 1)) (fib (- n 2))))))))

(def fact (Y (fn [fact]
               (fn [n] (if (= 0 n) 1 (* n (fact (dec n))))))))


(fib 35)   ;; 9227465
(fact 20)  ;; 2432902008176640000