SICP解答メモ＆解説 (問題1.9〜問題1.10）

問題1.9

以下の手続きを考える。

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

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

一つ目の手続きを置き換えると



(inc (+ (dec 4) 5))

(inc (inc (+ (dec 3) 5)))

(inc (inc (inc (+ (dec 2) 5))))

(inc (inc (inc (inc (+ (dec 1) 5)))))

(inc (inc (inc (inc 5))))

(inc (inc (inc 6)))

(inc (inc 7))

(inc 8)

9

になり線形再帰プロセスになることがわかる。

二つ目の手続きを置き換えると



(+ (dec 4) (inc 5))

(+ (dec 3) (inc 6))

(+ (dec 2) (inc 7))

(+ (dec 1) (inc 8))

9

になり、線形反復プロセスになることがわかる。

再帰プロセスと反復プロセスの違い

今のところの理解で言えば、再帰プロセスはステップ数（計算量）、解釈系が使用する記憶量が線形に増えるプロセスのことである。

例として、この問題を使って、ステップ数、記憶量をグラフにしてみた。xは、問題で定義した「+」の第一引数の値である。（逆に言えば、第二引数はステップ数、記憶量は関係しないと言える。）

また反復プロセスはステップ数は、線形的に増加してしまうが、解釈系が使用する記憶量はある値に固定（末尾再帰的）になる。