SICP 1.2.2 Tree Recursion - プログラミング再入門

3ヶ月ぶりの更新と書いたのが8月25日。それから4ヶ月。少しずつ読み進めて入るのですがまたまた久しぶりのアップデートとなりました。手続き呼び出しが実行されて行く様子の勉強の続きです。

ノート

計算過程が木構造になる例。

数学的定義をそのままプログラムにすると、その計算過程は極めて冗長である事が分かる。１段進む毎にfib自身を２回呼び、fib 0、fib 1は相当な回数呼ばれる。

In fact, it is not hard to show that the number of times the procedure will compute (fib 1) or (fib 0) (the number of leaves in the above tree, in general) is precisely Fib(n + 1).

図1.5を見て数えてみる。

n	fib nを計算するのにfib 0かfib 1を呼び出す回数	fib n
0	1	0
1	1	1
2	2	1
3	3	2
4	5	3
5	8	5
6	…	8

n=0の時はともかく、確かにfib 0かfib 1を呼び出す回数はfib n+1となっている。fibの一般式からφのn乗に比例して計算量が増える事になる。

In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.

一般に木構造再帰計算の必要なステップはノードの数に比例し、スペースは木の深さに比例する。
ここでは計算ステップは関数適用の回数の事で、スペースは保留されている関数が占めるメモリあるいはスタックの事。

フィボナッチ数の別の計算方法も紹介されている。引数として、fib n+1、fib n、n回目の計算までの残り回数の３つの引数を取る関数fib-iterを定義する。

fib n+1	fib n	n
1	0	0
1	1	1
2	1	2
3	2	3
5	3	4
8	5	5

fib-iter内でfib-iterを呼び出す際に保留されている計算は存在しないのでスペースは消費しない。fib-iterを呼び出す毎に足し算を１回、引き算を１回行うので、ステップ数は2n回。木構造再帰計算よりも効率が良い事は明白。

唯一残念なのは足し算を１回余計に行ってしまう所。fib nを得るのにfib n+1まで計算してしまう。

かと言って、木構造再帰計算が役に立たない訳ではない。木構造のデータを処理するには自然な方法だし、数を扱う関数であっても数学的定義そのままのプログラムで理解が容易である利点がある。

Example: Counting change

両替時の金種の組み合わせ計算の例。1ドルを、50,25,10,5,1セント硬貨で両替する時に、硬貨（金種）の組み合わせは何通りあるか。ある金額となる硬貨の組み合わせを数える。

金種をひとつ取り上げ

その金種を一切使わずに、総額を両替する問題
その金種を取り敢えず１回使って、残りの額を全ての金種で両替する問題

に分割する。

ピンと来る様な来ない様な感じだが、答えとなる全ての組み合わせが分かっていると仮定して、それらをグループ分けすると考える方が分かりやすいかも知れない。例えばある金種（50セント）を含んでいるグループと含んでいないグループに分けるとする。

分割された問題はそれぞれ同様に二つの問題に分割出来る。従って問題は枝分かれする様にどんどん分割される。分割された問題は金種が減っているか、金額が減っているので、どこかで必ず枝分かれは止まる事が分かる。
枝分かれの梢（葉）の部分は

金額を変えずに金種を減らしたら金種が無くなった。これは両替出来るパターンとは数えない。
ある金種を使ってその額を減らしたら総額が０となった。これは丁度両替出来たパターンと数える。
ある金種を使ってその額を減らしたら総額が負となった。総額よりもその金種の方が大きいのでその金種は使えず、両替出来たパターンとは数えない。

ちなみに、ある金種を使ってその額を減らした時に総額が正となった場合は、更に分割出来るのでまだそこでは分割は止まらない事を意味する。

教科書の関数を実行してみる。

> (count-change 100)
292
>

入力を全て引数で受け取る様にすると

実行結果

> (count-change 100 '(50 25 10 5 1))
292
>

フィボナッチ数の計算同様、この計算も冗長。効率の良い計算方法は？自力で考えるのは流石に無理。。。

Exercise 1.11

再帰的定義

実行結果

> (f 0)
0
> (f 1)
1
> (f 2)
2
> (f 3)
4
> (f 4)
11
> (f 5)
25
> (f 6)
59
>

繰り返し的定義

実行結果

> (fi 0)
0
> (fi 1)
1
> (fi 2)
2
> (fi 3)
4
> (fi 4)
11
> (fi 5)
25
> (fi 6)
59
>

Exercise 1.12

パスカルの三角形を左側に詰めて考えて、

何段目の何番目の数が何かを計算する関数を考える。

1段目、1番目は1
格段の最後（段数と同じ番）は1
それ以外は、上の段の同じ列と上の段のひとつ左の数の合計

実行してみる

> (pascal 1 1)
1
> (pascal 2 1)
1
> (pascal 2 2)
1
> (pascal 3 1)
1
> (pascal 3 2)
2
> (pascal 3 3)
1
> (pascal 4 1)
1
> (pascal 4 2)
3
> (pascal 4 3)
3
> (pascal 4 4)
1
> (pascal 5 1)
1
> (pascal 5 2)
4
> (pascal 5 3)
6
> (pascal 5 4)
4
> (pascal 5 5)
1
>

Exercise 1.13

フィボナッチ数列の一般式は与えられている。
$fib(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}$
展開すると
$fib(n) = \frac{\phi^n}{\sqrt{5}} - \frac{\psi^n}{\sqrt{5}}$
ここで
$\psi = \frac{1 - \sqrt{5}}{2} \approx -0.618033$
$\frac{\psi^n}{\sqrt{5}}$ の部分は、
n=0の時 $\frac{1}{\sqrt{5}}\approx 0.44721$
n=1の時 $\frac{\frac{1 - \sqrt{5}}{2}}{\sqrt{5}} \approx 0.27939$
とどんどん小さくなって行く。
fib(n)は整数で、 $\frac{\phi^n}{\sqrt{5}} - \frac{\psi^n}{\sqrt{5}}$ も整数。
かつ、 $\frac{\psi^n}{\sqrt{5}}$ は常に±0.5より0に近いので、fib(n)は $\frac{\phi^n}{\sqrt{5}}$ に最も近い整数と言える。