SICP読書録 #5 1.2.2 木の再帰

[hiroshi-manabe様の日本語訳](https://github.com/hiroshi-manabe/sicp-pdf)を使わせてもらいます。
練習問題等は[Gauche](http://practical-scheme.net/gauche/index-j.html)で実行。

[前回はこちら](https://qiita.com/shuetsu@github/items/58c8c656b74562a9e1bb)

# 1.2.2 木の再帰

任意の金額をコイン（50, 25, 10, 1セント）に両替するパターンの数は？

```1.2.2.scm
(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セントを両替する場合について見てみる。

```1.2.2.0.scm
> (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

```math
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.
```

これを計算する手続きを書け。反復プロセス版も。

```ex1_11.scm
(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))
```

実行結果。こんなに差が出る。

```ex1_11_result.scm
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
```

```ex1_12.scm
(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

再帰のお勉強と言えばおなじみのフィボナッチ関数。

```math
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)$を示す。

```math
\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}$との差をとると。

```math
\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}$なので。

```math
\left|\frac{\phi^n}{\sqrt{5}}\right| \lt 0.5
```

というわけで、$Fib(n)$ は $\varphi^n/\sqrt{5}$ に最も近い整数となる。

せっかくなので実装してみる。

```ex1_13.scm
(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)))
```

実行結果。

```ex1_13_result.scm
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
```