SICPラン④(p31~1.2 手続きとそれが生成するプロセス)

これまでは、プログラミングの組み立て方を学んできた。算術演算子を用いた単純な手続きを組み合わせ、ときに特殊形式のifを用いて複雑な手続きを組み立てた。（例えば、ある整数の平方根を求める手続き）

ここからは、それらの手続きをどのようにして用いればより効果が得られるかを学ぶ。いわば定石の習得に入る。

1.2.1 線形反復と反復

n! = n・(n-1)・(n-2)・・・3・２・１

階乗を計算する方法は二つ

①n・(n-1)!
②の答えに、数字をかけていく。そしてnまでカウントアップしていく、

という方法がある。

①に関しては、掛け算の連鎖により式が展開されその後縮約されていく。これを再帰(recursive process)プロセスと呼び、次に、インタプリタは計算のため計算プロセスを保持しておく必要がある。つまり展開する式の長さと計算に必要なステップ数はnに比例していることがわかる。ここまで含めて線形再帰プロセス(linear reucrisve process)と呼ばれる。

②の方法は、①と違って展開式が伸びることはない。なぜなら積に対してカウンターとなる数をかけ、カウンターがnになった時点でそれが階乗の答えとなる。このように展開式は伸びないが、ステップ数は①と同様にnに比例する。これを線形反復プロセス(linear iterative process)と呼ぶ。

練習問題 1.9
>|scheme|

(define (+ a b))
(if (= a 0) b (inc (+ (dec a) b)))

||<
上記の式の場合、式は再帰プロセスとなる。
しかし、以下の式においては

>|scheme|

(define (+ a b))
(if (= a 0) b (+ (dec a) (inc c)))

||<
ifの条件式以下で式が展開し、それは反復プロセスとなる。