Let's look at the solutions for the next of Clojure Koans -Recursion.
;recursion
(defn is-even? [n]
(if (= n 0)
__
(___ (is-even? (dec n)))))
;;;;;
; this one is beauty
; is based on flipping the current state algorithm
(defn is-even? [n]
(if (= n 0)
true
(not (is-even? (dec n)))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defn is-even-bigint?
[n]
(loop [n n
acc true]
(if (= n 0)
__
(recur (dec n) (not acc)))))
; this is direct application of above algo
; difference is we are now using the correct form namely
; recur
(defn is-even-bigint?
[n]
(loop [n n
acc true]
(if (= n 0)
true
(recur (dec n) (not acc)))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defn
recursive-reverse [coll]
__)
(defn
recursive-reverse [coll]
(loop [coll coll
reversed '()]
(if (empty? coll)
reversed
(recur (rest coll) (cons (first coll) reversed)))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defn factorial [n]
__)
(defn factorial [n]
(loop [n n
res 1]
(if (= 0 n)
res
(recur (dec n) (* n res)))))
;;;;;;;;;;;;;
"Recursion ends with a base case"
(= true (is-even? 0))
"And starts by moving toward that base case"
(= false (is-even? 1))
"Having too many stack frames requires explicit tail calls with
recur"
(= false (is-even-bigint? 100003N))
"Reversing directions is easy when you have not gone far"
(= '(1) (recursive-reverse [1]))
"Yet more difficult the more steps you take"
(= '(5 4 3 2 1) (recursive-reverse [1 2 3 4 5]))
"Simple things may appear simple."
(= 1 (factorial 1))
"They may require other simple steps."
(= 2 (factorial 2))
"Sometimes a slightly bigger step is necessary"
(= 6 (factorial 3))
"And eventually you must think harder"
(= 24 (factorial 4))
"You can even deal with very large numbers"
(<
1000000000000000000000000N (factorial 1000N))
"But what happens when the machine limits you?"
(<
1000000000000000000000000N (factorial 100003N)))
No comments:
Post a Comment