目录
Procedures and the Processes They Generate
1. Linear Recursion and Iteration
(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))
1 factorial = lambda n: 1 if n==1 else n*factorial(n-1)
(define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count)))
2. Tree Recursion
(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))
1 fib = lambda n: 0 if n==0 else ( 1 if n==1 else fib(n-1)+fib(n-2) )
(define (fib n) (fib-iter 1 0 n)) (define (fib-iter a b count) (if (= count 0) b (fib-iter (+ a b) a (- count 1))))
(define (count-change amount) (cc amount 5)) (define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc amount (- kinds-of-coins 1)) (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins))))) (define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 1) ((= kinds-of-coins 2) 5) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 25) ((= kinds-of-coins 5) 50)))
1 count_change = lambda amount: cc(amount, 5) 2 cc = lambda amount, kinds_of_coins: 1 if amount==0 else 0 if amount < 0 or kinds_of_coins == 0 else cc(amount, kinds_of_coins-1)+cc(amount-first_denomination(kinds_of_coins), kinds_of_coins) 3 first_denomination = lambda kinds_of_coins: 1 if kinds_of_coins==1 else 5 if kinds_of_coins==2 else 10 if kinds_of_coins==3 else 25 if kinds_of_coins==4 else 50 if kinds_of_coins==5 else 0
(count-change 100) 292
1 count_change(100)
3. Orders of Growth
4. Exponentiation
(define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1)))))