1.2.2 Tree Recursion - 一汁三菜

Fibonacci numbersの計算をrecursive processとiterative processの両方で実装してみせて、iterative processの方が性能が良い事を示した。けれども、recursive processが全ての場合において悪いというわけではない、という事も示唆していた。
fibonacci numbersを定義通りに書いたプログラムは、以下のrecursive process。

(define (fib n)
  (cond ((= n 0) 1)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) (fib (- n 2))))))

しかし、以下のiterative processでも出来るらしく。非再帰版もあるとは知っていたけど、こういう形だとは知らなかった。

(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))))

そして次はcounting changesの問題。ある金額の釣銭を払うのに使う小銭の組み合わせは、何通りあるかを求める問題。米ドル硬貨の名前は中学生の時に教わったはずなのに、それぞれ何セントになるのか覚えていなかったので、まずはそれから。

名称	価値
dime	10 US cent
nickel	5 US cent
penny	1 US cent

戦略は次の通り。aドルをn種類のコインで支払おうとした時の組み合わせは、

最初の種類のコイン以外でaドルを支払う組み合わせ。及び、
n種類のコインでa-dドル(d=最初の種類のコインの額面)を支払う組み合わせ。

例えば50, 25, 10, 5, 1セント硬貨がある時に1ドルを支払おうとしたら、

50セント硬貨以外で1ドルを支払う組み合わせ
全ての硬貨で50セント(=1ドル-50セント)を支払う組み合わせ

が、1ドルを支払う組み合わせになるという事らしい。…分からない。
話を単純にして、11セントを1, 5, 10セント硬貨で支払う組み合わせを考えてみる。この時の組み合わせを数え上げると、

(10, 1)
(5*2, 1)
(5, 1*6)
(1*11)

以上の4通り。で、上述のアルゴリズムを適用してみる。

1, 5セント硬貨で11セントを支払う組み合わせ。(5*2+1, 5+1*6, 1*10+1の3通り)
1. 1セント硬貨だけで11セントを支払う組み合わせ。 (1*11の1通り)
2. 1, 5セント硬貨だけで6セントを支払う組み合わせ。 (5+1, 1*6の2通り)
1, 5, 10セント硬貨で1セントを支払う組み合わせ。(1セント硬貨1枚だけの1通り)

確かに一致する。個人的にはなかなか直感的な理解は得られていないけど、確かに計算は出来ている。
もちろんこのアルゴリズムは、fibonacci numbersを求めたのと同じような無駄がある。
しかし、これを簡単にiterative processで実装するのは難しい。*1

Exercise 1.11

f by means of a recursive process

(define (f n)
  (if (< n 3)
    n
    (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

f by means of an iterative process

(define (f n)
  (if (< n 3)
    n
    (f-iter 2 1 0 3 n)))
(define (f-iter f1 f2 f3 count n)
  (if (> count n)
    f1
    (f-iter (+ f1 (* 2 f2) (* 3 f3)) f1 f2 (+ 1 count) n)))

Exercise 1.12

(define (pascal level index)
  (if (or (= index 0) (= index level))
    1
    (+ (pascal (- level 1) index) (pascal (- level 1) (- index 1)))))

pascalの三角形を描画する必要がなければ、こんな感じで良さそう。と言ってもこれは単に $_nC_m$ を求めているだけだけど。

Exercise 1.13

$Fib(n)$ 　が　 $\phi^n/\sqrt{5}$ 　に最も近い整数、但し　 $\phi=(1+\sqrt{5})/2$ 　である事を証明する。ヒントは数学的帰納法を使う事と、 $\psi=(1-\sqrt{5})/2$ 　を用いて　 $Fib(n)=(\phi^n-\psi^n)/\sqrt{5}$ 　を証明する事。

$n=0$ 　の時に、 $Fib(0)=(\phi^0-\psi^0)/\sqrt{5}=0$ 。
$n=1$ 　の時に、 $Fib(1)=(\phi-\psi)/\sqrt{5}=1$ 。
$n=k$ 　の時に、 $Fib(k)=(\phi^k-\psi^k)/\sqrt{5}$ が成り立つと仮定する。
　の時に、　を証明する。ここでFibonacci numbersの定義より、。これより、
1. $Fib(k+1)-Fib(k)-Fib(k-1)=0$ 　が成り立つ事を証明する。
2. $(\phi^{k+1}-\psi^{k+1})/\sqrt{5})-(\phi^k-\psi^k)/\sqrt{5})-(\phi^{k-1}-\psi^{k-1})/\sqrt{5})$
3. $=(\phi^{k+1}-\psi^{k+1})-(\phi^k-\psi^k)-(\phi^{k-1}-\psi^{k-1})$
4. $=\phi^{k-1}(\phi^2-\phi-1)-\psi^{k-1}(\psi^2-\psi-1)$
5. $=\phi^{k-1}\Big{(1+\sqrt{5})^2/4-(1+\sqrt{5}/2)-1\Big}-\psi^{k-1}\Big{(1-\sqrt{5})^2/4-(1-\sqrt{5}/2)-1\Big}$
6. $=0$
よって、 $Fib(n)=(\phi^n-\psi^n)/\sqrt{5}$ 　が証明された。

ここから最初の「 $Fib(n)$ 　が　 $\phi^n/\sqrt{5}$ 　に最も近い整数である」事を証明をする必要があるけど、これはギブアップ。分からなかった。

20:43追記

counting changesの戦略がようやく理解できた。aドルをn種類のコインで支払おうとした時の組み合わせは、

最初の種類のコインを1枚も使わずに、aドルを支払う組み合わせと、
最初の種類のコインを1枚だけ使って、aドルを支払う組み合わせ。

これなら理解できる。で、これを言い換えると、

最初の種類のコインを1枚も使わずに、最初のコイン以外の全てのコインでaドルを支払う組み合わせと、
最初の種類のコインを1枚だけ使って支払う事を決めてしまって、残りのa-dドル(d=最初の種類のコインの額面)を全てのコインで支払う組み合わせ。

が組み合わせの総数になると。なるほどなるほど。

*1:動的計画法で何とかなるかと思って実装しようとしたけど、話はそう簡単では無かった。