2 (:use [sicp.utils :only (square)]
3 [clojure.contrib.math :only (sqrt expt)]
4 [clojure.contrib.trace :only (dotrace)]))
10 (* n (factorial (- n 1)))))
12 ;; stack friendly version
17 (recur (- x 1) (* acc x)))))
21 (reduce * (range 1 (inc n))))
24 ;; user> (dotrace [factorial] (factorial 3))
25 ;; TRACE t2701: (factorial 3)
26 ;; TRACE t2702: | (factorial 2)
27 ;; TRACE t2703: | | (factorial 1)
28 ;; TRACE t2703: | | => 1
29 ;; TRACE t2702: | => 2
35 ;; sicp.chapter1.ch1_2> (dotrace [factorial] (factorial 6))
36 ;; TRACE t2778: (factorial 6)
37 ;; TRACE t2779: | (factorial 5)
38 ;; TRACE t2780: | | (factorial 4)
39 ;; TRACE t2781: | | | (factorial 3)
40 ;; TRACE t2782: | | | | (factorial 2)
41 ;; TRACE t2783: | | | | | (factorial 1)
42 ;; TRACE t2783: | | | | | => 1
43 ;; TRACE t2782: | | | | => 2
44 ;; TRACE t2781: | | | => 6
45 ;; TRACE t2780: | | => 24
46 ;; TRACE t2779: | => 120
47 ;; TRACE t2778: => 720
52 ;; sicp.chapter1.ch1_2> (dotrace [factorial2] (factorial2 6))
53 ;; TRACE t2806: (factorial2 6)
54 ;; TRACE t2806: => 720
58 (defn fact-iter [product counter max-count]
59 (if (> counter max-count)
61 (fact-iter (* product counter)
69 ;; user> (dotrace [factorial fact-iter] (factorial 6))
70 ;; TRACE t2378: (factorial 6)
71 ;; TRACE t2379: | (fact-iter 1 1 6)
72 ;; TRACE t2380: | | (fact-iter 1 2 6)
73 ;; TRACE t2381: | | | (fact-iter 2 3 6)
74 ;; TRACE t2382: | | | | (fact-iter 6 4 6)
75 ;; TRACE t2383: | | | | | (fact-iter 24 5 6)
76 ;; TRACE t2384: | | | | | | (fact-iter 120 6 6)
77 ;; TRACE t2385: | | | | | | | (fact-iter 720 7 6)
78 ;; TRACE t2385: | | | | | | | => 720
79 ;; TRACE t2384: | | | | | | => 720
80 ;; TRACE t2383: | | | | | => 720
81 ;; TRACE t2382: | | | | => 720
82 ;; TRACE t2381: | | | => 720
83 ;; TRACE t2380: | | => 720
84 ;; TRACE t2379: | => 720
85 ;; TRACE t2378: => 720
89 ;; observation: clojure loop-recur construct is essentially the same as
90 ;; the iterative version.
92 ;; section 1.2.2: Tree Recursion
96 :else (+ (fib (- n 1))
100 (defn fib-iter [a b count]
103 (fib-iter (+ a b) a (dec count))))
108 ;; example: counting changes
109 (defn first-denomination [kinds-of-coins]
110 (cond (= kinds-of-coins 1) 1
111 (= kinds-of-coins 2) 5
112 (= kinds-of-coins 3) 10
113 (= kinds-of-coins 4) 25
114 (= kinds-of-coins 5) 50))
117 (defn first-denomination [kinds-of-coins]
118 ({1 1 2 5 3 10 4 25 5 50} kinds-of-coins))
120 (defn cc [amount kinds-of-coins]
122 (or (< amount 0) (= kinds-of-coins 0)) 0
123 :else (+ (cc amount (- kinds-of-coins 1))
125 (first-denomination kinds-of-coins))
128 (defn count-change [amount]
135 ;; 1.2.4: exponentiation
139 (defn expt-iter [base counter product]
152 (* b (myexpt b (dec n)))))
155 (defn fast-expt [b n]
157 (even? n) (square (fast-expt b (/ n 2)))
158 :else (* b (fast-expt b (dec n)))))
162 ;;; Section 1.2.5: GCD
166 (mygcd b (rem a b))))
168 ;;; section 1.2.6 Primality testing.
172 (defn find-divisor [n test-divisor]
173 (cond (> (square test-divisor) n) n
174 (divides? test-divisor n) test-divisor
175 :else (find-divisor n (inc test-divisor))))
177 (defn smallest-divisor [n]
181 (= (smallest-divisor n) n))
184 ;; fermat's little theorem
185 (defn expmod [base exp m]
187 (even? exp) (rem (square (expmod base (/ exp 2) m))
189 :else (rem (* base (expmod base (dec exp) m))
193 (= a (expmod a n n)))
195 (defn fermat-test [n]
196 (try-it (+ 1 (rand-int (- n 1))) n))
198 (defn fast-prime? [n times]
199 (cond (= times 0) true
200 (fermat-test n) (fast-prime? n (dec times))