計算機プログラムの構造と解釈 1.2.2

復習

この節にでてくるfibonacci数や黄金比の性質やそれらの証明はすでに説明した。
fibonacci数列
黄金比

木構造再帰(tree recursion)

Fibonacci数を例にとってみる。

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

このコードは再帰的プロセスである。
(fib 5)を計算するには(fib 4)(fib 3)を計算する必要があり、その(fib 4)と(fib 3)もまた同様である。
最終的には(fib 1)と(fib 0)の計算となるが、これらの計算回数（ステップ数ではない。ステップ数は節の数に比例する）は、F(n)のときF(n+1)回となる。
これは数学的帰納法を用いれば証明できる。
またF(n)はに最も近い整数であるので、
F(n)の値は指数的に増加することがわかる。


そして木構造再帰のステップ数は指数的に増加する。ステップ数は節の数に比例する。

必要なスペースは、計算中のノードの深さを知っていればよいので、入力に対して線形にしか増えない。必要なスペースは木構造の最大の深さに比例する。

fibonacci数列の反復的プロセス

変数a,bをa=F(1)=1,b=F(0)=0で初期化して、
a = a+b
b = a
としてn回繰り返すと、a=F(n+1),b=F(n)となっている。
ステップ数はnに線形に増加している。線形反復プロセスである。

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

木構造再帰のメリット

その１
直感的にコードを記述できること。
反復的プロセスを生成する反復的アルゴリズムを作り出すのは難しい。
木構造を生成してから、メモ化などによって工夫を凝らしていくことで改善。
アルコリズムは直感的で解りやすいし、速いし、で良いとこ取りを狙う。


その２
階層構造のデータを扱うプロセスを考えるときに強力な手法。
解釈系自身は式を木構造再帰的プロセスを使って評価している。

両替問題

※ぶっちゃけ、この両替問題の意図がわからない。何を学習させようとしているの？？
本の例題は「１ドルを50,25,10,5,1セントで両替する場合の数は？」だが、
ここでは問題を簡単にするために、10セントを5,1セントで両替する問題にする。

両替対象の金額をa,両替する硬貨の種類をnとすると、a=10,n=2である。
このときの両替の場合の数は、
「5セントを使わないで両替した場合の数+5セントを使って両替した場合の数」
となることは明白である。
このとき、後者には工夫の余地がある。
10セントを「必ず５セントを使って」5セントと１セントで両替するときの場合の数は、
(10-5=)5セントを5セントと1セントで両替するときの場合の数と等しい。
つまり、
(a=10,n=2)は(a=5,n=2)と(a=10,n=1)に分けられる。
少ない金額の問題に再帰的に縮小させることができる。

具体的には次の規程が必要となる。

• aが0なら、両替の場合の数は1:割り切れたから両替可能


• aが0より少なければ両替の場合の数は0 : 割りきれてない


• nが0なら、両替の場合の数は0 : 0種類だから当然、終了条件になる

(define (count-change amount)
(cc amount 2))

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

これはかなり冗長な木構造再帰的プロセスを生成する。
しかしより良い明白なアルゴリズムはない。