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

1.2 手続きと,その手続きによって生成されるプロセス

再帰的手続き、再帰的プロセス、反復的プロセスについて学ぶ。
※再帰的手続きだから再帰的プロセスとなるのではない。

1.2.1 線形再帰と反復

線形再帰プロセスを生成する手続き

(define (factorial n )
(if (= n 1)
1
(* n (factorial (- n 1)))))

これを置き換えモデルにすると

線形再帰プロセス
(factorial 4)
(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24

プロセスの形が横に伸びて(膨張)してから、縮小していっている。
これは遅延演算(deferred operations)の列を作るときに起こる。
下方向の流れがステップ数、横が覚えていなければならない演算の列の長さ。
ステップ数はnに線形。
この場合、列の長さもnに線形である。記憶しなればならない列の長さも線形に成長する場合、
線形再帰的プロセス(linear recursive process)という。

反復的プロセスを生成する手続き

(define (factorial n)
(define (iter product counter)
(if  (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))

反復的プロセス
(factorial 4)
(iter 1  1)
(iter 1  2)
(iter 2  3)
(iter 6  4)
(iter 24 5)
24

このプロセスは横に膨張しない。
各ステップで覚えておく必要があるのは product,counterだけである。
一定数のレジスタだけ用意すればよいのでハードウェアと相性がいい。
必要なステップ数がnに線形に成長する場合、線形反復的プロセスと呼ぶ。


※注意
再帰プロセス + 遅延演算列が線形 = 線形再帰プロセス
反復プロセス + ステップ数が線形 = 線形反復プロセス

C言語の再帰手続きで反復的プロセスは不可能

設計上無理。原理的には反復的であっても、列が成長するように設計されている。
反復的プロセスは、do,while,until,for,whileのような特殊目的の
「ループ構造」を必要とする。


与太話

lisp:ループだせぇw
C：ループ使わないで何でもかんでも再帰とかマジキチ

らしい。


再帰的手続きで反復的プロセスができる性質をもつ実装を末尾再帰的という。
これは後の3章で学習する。