hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。
1.2.2 木の再帰
任意の金額をコイン（50, 25, 10, 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つ減らした場合のパターン数と、その種類のコインを1つ採用した場合のパターン数を再帰的に足していく。
呼び出しの木構造はすぐ大きくなってしまうであろう。ためしに1セントと5セントのみを使って10セントを両替する場合について見てみる。
> (cc 10 2)
> (+ (cc 10 1) (cc 5 2)) ; まずは (cc 10 1) を展開してみる
> (+ (+ (cc 10 0) (cc 9 1)) (cc 5 2))
> (+ (+ (cc 10 0) (+ (cc 9 0) (cc 8 1))) (cc 5 2))
> (+ (+ (cc 10 0) (+ (cc 9 0) (+ (cc 8 0) (cc 7 1)))) (cc 5 2))
> (+ (+ (cc 10 0) (+ (cc 9 0) (+ (cc 8 0) (+ (cc 7 0) (cc 6 1))))) (cc 5 2))
> (+ (+ (cc 10 0) (+ (cc 9 0) (+ (cc 8 0) (+ (cc 7 0) (+ (cc 6 0) (cc 5 1)))))) (cc 5 2))
> (+ (+ (cc 10 0) (+ (cc 9 0) (+ (cc 8 0) (+ (cc 7 0) (+ (cc 6 0) (+ (cc 5 0) (cc 4 1))))))) (cc 5 2))
> (+ (+ (cc 10 0) (+ (cc 9 0) (+ (cc 8 0) (+ (cc 7 0) (+ (cc 6 0) (+ (cc 5 0) (+ (cc 3 0) (cc 2 1)))))))) (cc 5 2))
> (+ (+ (cc 10 0) (+ (cc 9 0) (+ (cc 8 0) (+ (cc 7 0) (+ (cc 6 0) (+ (cc 5 0) (+ (cc 3 0) (+ (cc 2 0) (cc 1 1))))))))) (cc 5 2))
> (+ (+ (cc 10 0) (+ (cc 9 0) (+ (cc 8 0) (+ (cc 7 0) (+ (cc 6 0) (+ (cc 5 0) (+ (cc 3 0) (+ (cc 2 0) (+ (cc 1 0) (cc 0 1)))))))))) (cc 5 2))
...
と、こんな感じですぐ書ききれないほどになる。再帰手続きはわかりやすくていいんだけど、計算空間の増え方に気をつけなければならない。
例えば、ccの結果をキャッシュしておくとかすればいいんじゃね？（3章でやるみたい）
練習問題 1.11
f(x) = \left\{
\begin{array}{ll}
n & (n \lt 3) \\
f(n-1)+2f(n-2)+3f(n-3) & (n \geq 3)
\end{array}
\right.
これを計算する手続きを書け。反復プロセス版も。
(define (ex1_11 n)
(if (< n 3)
n
(+ (ex1_11 (- n 1)) (* 2 (ex1_11 (- n 2))) (* 3 (ex1_11 (- n 3))))))
; 反復プロセス版
(define (ex1_11_iter n)
(define (iter a b c count)
(if (= count 0)
c
(iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))
(iter 2 1 0 n))
実行結果。こんなに差が出る。
gosh> (time (ex1_11 30))
;(time (ex1_11 30))
; real 3.526
; user 3.520
; sys 0.000
61354575194
gosh> (time (ex1_11_iter 30))
;(time (ex1_11_iter 30))
; real 0.000
; user 0.000
; sys 0.000
61354575194
練習問題1.12
パスカルの三角形の要素を求める。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
(define (ex1_12 r c)
(if (or (= c 0) (= c r))
1
(+ (ex1_12 (- r 1) c) (ex1_12 (- r 1) (- c 1)))))
練習問題1.13
再帰のお勉強と言えばおなじみのフィボナッチ関数。
Fib(x) = \left\{
\begin{array}{ll}
0 & (n = 0) \\
1 & (n = 1) \\
Fib(n-1)+Fib(n-2) & (n \geq 2)
\end{array}
\right.
$Fib(n)$ が $\varphi^n/\sqrt{5}$ に最も近い整数であることを証明せよ。$\varphi=(1+\sqrt{5})/2$とする。
ヒント：$\phi=(1-\sqrt{5})/2$ と置く。 $Fib(n)=(\varphi^n-\phi^n)/\sqrt{5}$ を証明せよ。
ちなみに$\varphi$、$\phi$は黄金比。すなわち$\varphi^2=\varphi+1$、$\phi^2=\phi+1$。
すくなくとも$Fib(0)=0$、$Fib(1)=1$は成り立つ。そこで$Fib(n)=Fib(n-1)+Fib(n-2)$を示す。
\begin{align}
Fib(n-1)+Fib(n-2) &= \frac{(\varphi^{n-1}-\phi^{n-1}) + (\varphi^{n-2}-\phi^{n-2})}{\sqrt{5}}\\
&=\frac{(\varphi^{n-2}(\varphi+1)+\phi^{n-2}(\phi+1))}{\sqrt{5}}\\
&=\frac{(\varphi^n+\phi^n)}{\sqrt{5}}
\end{align}
これで、$Fib(n)=(\varphi^n-\phi^n)/\sqrt{5}$は証明できた。
$\varphi^n/\sqrt{5}$との差をとると。
\left|\frac{(\varphi^n+\phi^n)}{\sqrt{5}} - \frac{\varphi^n}{\sqrt{5}}\right| = \left|\frac{\phi^n}{\sqrt{5}}\right|
$\sqrt{5} \fallingdotseq 2.2360...$, $\phi \fallingdotseq -0.61803...$より、$|\phi^n| \lt 0.5 \times \sqrt{5}$なので。
\left|\frac{\phi^n}{\sqrt{5}}\right| \lt 0.5
というわけで、$Fib(n)$ は $\varphi^n/\sqrt{5}$ に最も近い整数となる。
せっかくなので実装してみる。
(define phi (/ (+ 1 (sqrt 5)) 2))
(define varphi (/ (- 1 (sqrt 5)) 2))
(define (fib-neighbor n)
(/ (expt phi n) (sqrt 5)))
(define (fib n)
(/ (- (expt phi n) (expt varphi n)) (sqrt 5)))
実行結果。
gosh> (fib-neighbor 0)
0.4472135954999579
gosh> (fib 0)
0.0
gosh> (fib-neighbor 1)
0.7236067977499789
gosh> (fib 1)
1.0
gosh> (fib-neighbor 2)
1.1708203932499368
gosh> (fib 2)
1.0
gosh> (fib-neighbor 3)
1.8944271909999157
gosh> (fib 3)
2.0
gosh> (fib-neighbor 4)
3.065247584249853
gosh> (fib 4)
3.0000000000000004
gosh> (fib-neighbor 5)
4.959674775249769
gosh> (fib 5)
5.000000000000001