这次主要想通过几个sicp的题目来说明递归计算过程和迭代计算过程。
（1）阶乘
;递归计算过程
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
;迭代计算过程
(define (fact-iter counter result)
(if (= counter 1)
result
(fact-iter (- counter 1) (* counter result))))
(define (factorial n)
(fact-iter n 1))
（2）斐波拉契数列（普通方法）
;递归计算过程（cond 可以类比为C++中的switch，只是它还可以判断范围）
(define (Fib n)
(cond
((= n 0) 0)
((= n 1) 1)
(else (+ (Fib (- n 1))
(Fib (- n 2))))))
;迭代计算过程
(define (Fib-iter n a b)
(if (= n 0)
a
(Fib-iter (- n 1) b (+ a b))))
(define (Fib n)
(Fib-iter n 0 1))
（3）两个正整数加法（假设存在过程inc（递增1）和过程dec（递减1））
;n++
(define (inc n)
(+ n 1))
;n--
(define (dec n)
(- n 1))
;递归计算过程
(define (+ a b)
(if (= 0 a)
b
(inc (+ (dec a) b))))
;迭代计算过程
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
（4）两个正整数乘法（假设存在过程double（翻倍）和过程halve（减半），基于这个两个已存在的过程，这个算法可以在对数步骤求出结果）
;2*n
(define (double n)
(* n 2))
;n/2
(define (halve n)
(/ n 2))
;判断是否为偶数
(define (even? n)
(= 0 (remainder n 2)))
;需要注意的是：当b为偶数时, a*b = 2 * (a * (b / 2))；当b为奇数时, a*b = a*(b-1) + a
;递归计算过程
(define (* a b)
(cond
((= b 0) a)
((even? b) (double (* a (halve b))))
(else (+ a (* a (- n 1))))))
;迭代计算过程
(define (*-iter a b result)
(cond
((= b 0) result)
((even? b) (*-iter (double a) (halve b) result))
(else (*-iter a (- b 1) (+ a result)))))
(define (* a b)
(*-iter a b 0))
（5）求幂b^n（对数步骤）
;n^2
(define (square n)
(* n n))
;需要注意的是：当n为偶数时, b^n = (b^(n/2))^2；当n为奇数时, b^n = b^(n-1) * b
;递归计算过程
(define (fast-expt b n)
(cond
((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
;迭代计算过程
(define (fast-expt-iter b n result)
(cond
((= n 0) result)
((even? n) (fast-expt-iter (square b) (/ n 2) result))
(else (fast-expt-iter b (- n 1) (* b result)))))
(define (fast-expt b n)
(fast-expt-iter b n 1))
（6）斐波拉契数列（对数步骤）
;这个算法基于一种比较巧妙的变换规则，用类似于fast-expt的方式压缩求解步骤。
;在fib-iter普通算法中，计算过程中的变换方式为a=b, b=a+b, 将此看作为T变换，也就是说Fib通过n次T变换就可以得到结果。
;而T变换可以看作是变换族Tpq中p=0且q=1的特殊情况，其中a = a*p + b*q, b = a*q + b*q + b*p
;可以证明我们应用Tpq变换两次，等同于应用Tp'q'变换一次，其中p' = p*p + q*q, q' = 2*p*q + q*q
;迭代计算过程
(define (fib-iter n a b p q)
(cond
((= n 0) a)
((even? n) (fib-iter (/ n 2)
a
b
(+ (* p p) (* q q))
(+ (* 2 p q) (* q q))))
(else (fib-iter (- n 1)
(+ (* a p) (* b q))
(+ (* a q) (* b q) (* b p))
p
q))))
(define (fib n)
(fib-iter n 0 1 0 1))