計算機プログラムの構造と解釈 問題1.9

次の手続きを置換えモデルを使い、それぞれの手続きが(+ 4 5)を評価する時に生成するプロセスを示せ。そのプロセスは反復的か再帰的か。

incはインクリメント、decはデクリメントを行う手続き

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

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

前者のプロセスは

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

となるので、再帰的プロセス。かつaに線形に列が生成されるので、線形再帰的プロセス。

後者のプロセスは

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

となるので、反復的プロセス。かつaに線形にステップ数が増加するので、線形反復的プロセス。