1.2.1~1.2.3

1.2.1 線形再帰と反復

　階上計算を行う2つの手続きが紹介されている。
・線形再帰的プロセス：計算に遅延演算の列を使用するプロセス
・線形反復的プロセス：計算にプロセスを完全に記述する状態変数を使用プロセス

　手続きとプロセスは明確に異なる。ここで紹介されている例は手続きはいずれも再帰的であるが、その手続きを実行時のプロセスはそれぞれ上記のように異なる。

　また各プロセスの接頭辞として「線形」がついているが、これはプロセスの「ステップ数」や「スペース」がnに対して線形に成長するからである。（後に1.2.4にて、ステップ数が対数的に成長する例も紹介される）

　一般に線形反復的プロセスとなる手続きを考えるのは、線形再帰的プロセスとなる手続きよりも難しい（後に問題1.16のように不変量を定義する手法が紹介される）。

　後者の手続きは次節のフィボナッチ数の計算プロセスのように、対象を直感的に手続きに書き下すだけですむ場合もある。

1.2.2　木構造再帰

　tree recursionを木構造再帰と訳されていますが、再帰的木構造などのほうが日本語としてよいと思います…。

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

　上の手続きによるフィボナッチ数の計算プロセスは再帰的木構造を形成し、計算回数が指数関数的に増大してしまい、非常に非効率。

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

　こちらの手続きによるフィボナッチ数の計算プロセスは線形反復に収まる。実装方法を変えることで、計算プロセスを線形反復に抑えられるケースが存在する。

前者と後者では手続きの構成がまったく異なる。たとえば前者では初期値(0および1)はcondの場合分けの中に含まれているが、後者では手続きとして与える引数の中に与えられている。

　与えられた金額のコインの両替数をカウントするプログラムも、フィボナッチ数の計算と同じく再帰的プロセスとなる（ただしこちらは木構造の再帰的拡大ではなく、再帰的縮小となる）。

1.2.3　増加の程度

計算の資源を消費する速度は、その計算の実行するプロセスに依存する。そうした資源の消費する尺度として、ステップとスペースを用いる。

（ステップ/スペースをそれぞれ以下のようなものと解釈しました。）
ステップ：式を評価するために必要なプロセスの評価回数
スペース：計算のプロセスを可視化したときにサイズ