Skip to content

Instantly share code, notes, and snippets.

Last active Oct 3, 2021
What would you like to do?
CPS can't reduce the time complexity...
(defn fac [n]
(if (zero? n) 1
(* n (fac (dec n)))))
(defn fac-t [n acc] ; n 1
(if (zero? n) acc
(recur (dec n) (* acc n))))
(defn fac-c [n f] ; n identity
(if (zero? n) (f 1)
(recur (dec n) #(f (* n %)))))
(defn fac-a [n k]
(let [b (zero? n)]
(if b
(k 1)
(let [nm1 (dec n)]
(fac-a nm1 #(let [tn (* % n)]
(k tn)))))))
(defn fib [x]
(if (< x 2) x
(+ (fib (dec x))
(fib (- x 2)))))
; hint example:
; A + b * x
; A + b * (C + d * x) -> A+bC + bd*x
(defn fib-t [x a b] ; x 0 1
(if (zero? x) a
(recur (dec x) b (+ a b))))
(defn fib-c [x f] ; x identity
(if (< x 2) (f x)
(recur (dec x) (fn [r1]
(fib-c (- x 2) (fn [r2]
(f (+ r1 r2))))))))
(defn fib-a [x k]
(let [b (< x 2)]
(if b
(k x)
(let [xm1 (dec x)]
(fib-a xm1 (fn [r1]
(let [xm2 (- x 2)]
(fib-a xm2 (fn [r2]
(let [r (+ r1 r2)]
(k r)))))))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment