SICP（1.2 手続きとその生成するプロセス） - selflearn @ ウィキ

『1.2 手続きとその生成するプロセス』

まとめ

Lispにおいて、再帰処理には

• 再帰的プロセス
• 反復的プロセス

の2種類があり、使用するリソース（これは増加の度合いをΘ(f(n))で表す）に違いがある。
Cでは構文として再帰表現を用いた場合は必ず再帰的プロセスとなり、再帰の繰り返しでスタック領域が消費されていくが、Lispでは末尾再帰表現となっていれば反復的プロセスとみなされ、スタックを消費しない（ループで表現される）。

反復的プロセスを書くコツは、計算がいつ終えても大丈夫なように「状態」を表すパラメータを用意しておくこと。

各小節の内容

1.2.1 線形再帰と反復

再帰には2種類ある、という話。

再帰的プロセス	アルゴリズムの本でよく言われる再帰のこと。伸長時はスタックに詰まれていき、収縮時に演算が実際に実行されていく
反復的プロセス	状態変数とともに再帰が反復されるため、評価の伸長、収縮時にスタックを記憶しておく必要がない（スタック領域を消費しない）

後者はCではfor/whileループでしか実現できないが、Schemeでは末尾再帰により通常の再帰形式の記述でも反復的プロセスが実現できるとのこと。
（IEEE規格で求められているらしい）
知らなかった。

インタプリタは、これまで知っていた再帰と末尾再帰をどういう風に区別して実行するんだろう？

5章で実際に末尾再帰Schemeを実際するらしいので、これも楽しみ。

あと、言葉の違いに気をつけろとして再帰という表現の2種類を挙げている。

• 再帰的プロセス
• 再帰的手続き

後者が「構文が再帰表現である」かどうかのみを意味していて、前者は「実行時に再帰的（≠反復的）である」ことを示す。

1.2.2 木構造再帰

木構造再帰は、スタックあまり消費しないものの計算回数が指数的に増えていくことが問題。同じような計算を何回も繰り返したりとか。

ポイントは、木構造となる手続きからいくつかの部分をより効率的にすること。本書内脚注では、その一例として「同じような計算に対してはテーブルを持たせてしまう（ことで余計な計算を回避する）」とある。

1.2.3 増加の程度

計算の資源消費がどのようなオーダーで行われていくかを記述する方法について。
ここではΘ(n)やΘ(n^2)というように、増加の速度を大文字のシータで表している。

結局のところ、O記法と同じ。

1.2.4 べき乗

資源の消費ペースはアルゴリズムによって抑えられるという事例の紹介。
べき乗を計算する時も、バカ正直に計算するのではなくb^n=(b^(n/2))またはb*b^(n-1)というように分割していくことで、対数的ステップ数で実現出来るという話。さらに、それに状態変数という概念を組み合わせて反復的プロセスを実現する方法が書かれている。

状態の移り変わりでも変化しないよう、想定している式と状態変数によって不変量を定義する方法は、面白かった。反復によって値がドンドン答に近づいていくのが見ていて楽しいから。

1.2.5 最大公約数

ユークリッドの互除法を紹介。以下のように、とても簡単に実現出来るのを見ると、Schemeは「力強い」なあと思う。

(define (gcd a b)
  (if (= b 0) a
      (gcd b (remainder a b))))

1.2.6 例:素数性のテスト

ある値nが素数かどうかを調べるにあたってのアルゴリズムを2パターンで紹介。

除数を探索する方法

2から順にnを割っていって割り切れる整数があるかどうかを探索していく方法。

確率的に調べる方法

ランダムな値aによって割り切れるかどうかを調べ、指定回数繰り返しても割り切れる数値が見つからなければ素数（である確率が高い）とみなす方法。「確率的アルゴリズム」と言う。

ここで数学的な用語が出てきたので転載。

Fermatの小定理

nを素数、aをnより小さい正の任意の整数とすると、aのn乗はnを法としてaと合同である（＝a^n（nは素数）は、それぞれnで割ったときの剰余がaである）。

よくFermatの小定理の説明で出てくるのは「任意の素数pについて、pと互いに素なaについて、a^(p-1)≡1 (mod p)が成り立つ」という記述だけれど、SICPでは上記のように書かれていた。
同じことを言っているのかどうかよく分かっていないので、それは今後の宿題としよう。

２つの数は、両者をnで割ったときに同じ剰余を持てば、「nを法として合同(congruent modulo n)」という。また、数aをnで割った剰余を「nを法としたaの剰余(remainder of a modulo n)」、「nを法としたa(a modulo n)」という