exercise-9.scm (7363B)
1 (define-library (sicp solutions chapter-3 exercise-9) 2 (import (scheme base)) 3 4 (begin 5 (define (recursive-factorial-global-environment) 6 (define (factorial n) 7 (if (= n 1) 8 1 9 (* n (factorial (- n 1))))) 10 11 ;;; +--------------------+ 12 ;;; | | 13 ;;; global -->| factorial: --+ | 14 ;;; env | | | 15 ;;; +--------------|-----+ 16 ;;; +---+ ^ 17 ;;; | | 18 ;;; V | 19 ;;; .---.---. | 20 ;;; | O | O-+---+ 21 ;;; `-|-^---' 22 ;;; | 23 ;;; V 24 ;;; parameters: n 25 ;;; body: (if (= n 1) 26 ;;; 1 27 ;;; (* n (factorial (- n 1)))) 28 ;;; 29 ;;; global env 30 ;;; | 31 ;;; V 32 ;;; +----+ 33 ;;; | | E1 (factorial 6) 34 ;;; | | | 35 ;;; | | V 36 ;;; | | +------+ 37 ;;; | | | n: 6 | (if (= n 1) 38 ;;; | | +------+ 1 39 ;;; | | | (* n (factorial (- n 1)))) 40 ;;; | |<--+ 41 ;;; | | 42 ;;; | | E2 (factorial 5) 43 ;;; | | | 44 ;;; | | V 45 ;;; | | +------+ 46 ;;; | | | n: 5 | (if (= n 1) 47 ;;; | | +------+ 1 48 ;;; | | | (* n (factorial (- n 1)))) 49 ;;; | |<--+ 50 ;;; | | 51 ;;; | | E3 (factorial 4) 52 ;;; | | | 53 ;;; | | V 54 ;;; | | +------+ 55 ;;; | | | n: 4 | (if (= n 1) 56 ;;; | | +------+ 1 57 ;;; | | | (* n (factorial (- n 1)))) 58 ;;; | |<--+ 59 ;;; | | 60 ;;; | | E4 (factorial 3) 61 ;;; | | | 62 ;;; | | V 63 ;;; | | +------+ 64 ;;; | | | n: 3 | (if (= n 1) 65 ;;; | | +------+ 1 66 ;;; | | | (* n (factorial (- n 1)))) 67 ;;; | |<--+ 68 ;;; | | 69 ;;; | | E5 (factorial 2) 70 ;;; | | | 71 ;;; | | V 72 ;;; | | +------+ 73 ;;; | | | n: 2 | (if (= n 1) 74 ;;; | | +------+ 1 75 ;;; | | | (* n (factorial (- n 1)))) 76 ;;; | |<--+ 77 ;;; | | 78 ;;; | | E6 (factorial 1) 79 ;;; | | | 80 ;;; | | V 81 ;;; | | +------+ 82 ;;; | | | n: 1 | (if (= n 1) 83 ;;; | | +------+ 1 84 ;;; | | | (* n (factorial (- n 1)))) 85 ;;; | |<--+ 86 ;;; +----+ 87 ) 88 89 (define (iterative-factorial-global-environment) 90 (define (factorial n) 91 (fact-iter 1 1 n)) 92 93 (define (fact-iter product 94 counter 95 max-count) 96 (if (> counter max-count) 97 product 98 (fact-iter (* counter product) 99 (+ counter 1) 100 max-count))) 101 102 ;;; +------------------------------+ 103 ;;; | fact-iter: -------------+ | 104 ;;; global -->| | | 105 ;;; env | factorial: --+ | |<-+ 106 ;;; +--------------|----------|----+ | 107 ;;; +---+ ^ | | 108 ;;; | | | | 109 ;;; V | V | 110 ;;; .---.---. | .---.---. | 111 ;;; | O | O-+---+ | O | O-+---+ 112 ;;; `-|-^---' `-|-^---' 113 ;;; | | 114 ;;; V +--------+ 115 ;;; parameters: n | 116 ;;; body: (fact-iter 1 1 n) +-> parameters: product, counter, max-count 117 ;;; body: (if (> counter max-count) 118 ;;; product 119 ;;; (fact-iter (* counter product) 120 ;;; global env (+ counter 1) 121 ;;; | max-count)) 122 ;;; V 123 ;;; +----+ 124 ;;; | | E1 (factorial 6) 125 ;;; | | | 126 ;;; | | V 127 ;;; | | +------+ 128 ;;; | | | n: 6 | (fact-iter 1 1 n) 129 ;;; | | +------+ 130 ;;; | | | 131 ;;; | |<--+ 132 ;;; | | 133 ;;; | | E2 (fact-iter product counter max-count) 134 ;;; | | | 135 ;;; | | V 136 ;;; | | +--------------+ 137 ;;; | | | product: 1 | (if (> counter max-count) 138 ;;; | | | counter: 1 | product 139 ;;; | | | max-count: 6 | (fact-iter (* counter product) 140 ;;; | | +--------------+ (+ counter 1) 141 ;;; | | | max-count)) 142 ;;; | |<--+ 143 ;;; | | 144 ;;; | | E3 (fact-iter product counter max-count) 145 ;;; | | | 146 ;;; | | V 147 ;;; | | +--------------+ 148 ;;; | | | product: 1 | (if (> counter max-count) 149 ;;; | | | counter: 2 | product 150 ;;; | | | max-count: 6 | (fact-iter (* counter product) 151 ;;; | | +--------------+ (+ counter 1) 152 ;;; | | | max-count)) 153 ;;; | |<--+ 154 ;;; | | 155 ;;; | | E4 (fact-iter product counter max-count) 156 ;;; | | | 157 ;;; | | V 158 ;;; | | +--------------+ 159 ;;; | | | product: 2 | (if (> counter max-count) 160 ;;; | | | counter: 3 | product 161 ;;; | | | max-count: 6 | (fact-iter (* counter product) 162 ;;; | | +--------------+ (+ counter 1) 163 ;;; | | | max-count)) 164 ;;; | |<--+ 165 ;;; | | 166 ;;; | | E5 (fact-iter product counter max-count) 167 ;;; | | | 168 ;;; | | V 169 ;;; | | +--------------+ 170 ;;; | | | product: 6 | (if (> counter max-count) 171 ;;; | | | counter: 4 | product 172 ;;; | | | max-count: 6 | (fact-iter (* counter product) 173 ;;; | | +--------------+ (+ counter 1) 174 ;;; | | | max-count)) 175 ;;; | |<--+ 176 ;;; | | 177 ;;; | | E6 (fact-iter product counter max-count) 178 ;;; | | | 179 ;;; | | V 180 ;;; | | +--------------+ 181 ;;; | | | product: 24 | (if (> counter max-count) 182 ;;; | | | counter: 5 | product 183 ;;; | | | max-count: 6 | (fact-iter (* counter product) 184 ;;; | | +--------------+ (+ counter 1) 185 ;;; | | | max-count)) 186 ;;; | |<--+ 187 ;;; | | 188 ;;; | | E7 (fact-iter product counter max-count) 189 ;;; | | | 190 ;;; | | V 191 ;;; | | +--------------+ 192 ;;; | | | product: 120 | (if (> counter max-count) 193 ;;; | | | counter: 6 | product 194 ;;; | | | max-count: 6 | (fact-iter (* counter product) 195 ;;; | | +--------------+ (+ counter 1) 196 ;;; | | | max-count)) 197 ;;; | |<--+ 198 ;;; | | 199 ;;; | | E8 (fact-iter product counter max-count) 200 ;;; | | | 201 ;;; | | V 202 ;;; | | +--------------+ 203 ;;; | | | product: 720 | (if (> counter max-count) 204 ;;; | | | counter: 7 | product 205 ;;; | | | max-count: 6 | (fact-iter (* counter product) 206 ;;; | | +--------------+ (+ counter 1) 207 ;;; | | | max-count)) 208 ;;; | |<--+ 209 ;;; +----+ 210 )))