牛顿法求平方根
如果对x的平方根有一个估计值y，则可以通过求y和x/y的平均值可以得到一个更好的猜测。
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (square x) (* x x))
(define (sqrt x)
(sqrt-iter 1.0 x))
(sqrt 10)
求立方根
(define (cubrt-iter guess x)
(if (good-enough? guess x)
guess
(cubrt-iter (improve guess x)
x)))
(define (improve guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
(define (square x) (* x x))
(define (cubic x) (* x (square x)))
(define (good-enough? guess x)
(< (abs (- (cubic guess) x)) 0.0001))
(define (cubrt x)
(cubrt-iter 1.0 x))
(cubrt 10)
阶乘
线性递归的计算过程
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
(factorial 5)
线性迭代的计算过程，
(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)))
(factorial 5)
在迭代的情况中，在计算的任何一点，上面的三个变量都提供了有关计算状态的一个完整描述。而递归则需要维持一个更多更长的信息。
树形递归之fib
;递归
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 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))))
换零钱问题
将金钱数a换成n中不同类型币值的任意组合有多少种组合方式。
使用一种递归的方法可以很容易地表示这个问题，首先将币种进行从大到小排序，然后将问题分为两种情况。
（1）将全部钱a换成除了第一种币值以外的钱
（2）将钱a-d换成所有币值的组合，其中d为第一种币值。
(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)))
(count-change 100)
