[SICP] 問題 1.09 : 反復的プロセスと再帰的プロセス

次の二つの手続きはどちらも, 引数を1増やす手続きincと, 引数を1減らす手続き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)を評価する時に生成するプロセスを示せ. そのプロセスは反復的か再帰的か.

置き換えモデルを使い, 生成するプロセスを書いてみます. まず1つ目の手続きが生成するプロセスです.

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

次に, 2つ目の手続きが生成するプロセスです.

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

処理系を使って生成するプロセスを確認します. 問題文の手続きを定義します. 手続き「+」は定義済みのため, １つ目の手続きを「+#」, ２つ目の手続きを「+$」としています. また, 手続きが生成するプロセスを観察するためにtraceを使用します.

(require (lib "racket/trace.ss"))

(define (inc x)
  (+ x 1))

(define (dec x)
  (- x 1))

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

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

(trace +# +$)

実行結果は次のようになりました.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (+# 4 5)
>(+# 4 5)
> (+# 3 5)
> >(+# 2 5)
> > (+# 1 5)
> > >(+# 0 5)
< < <5
< < 6
< <7
< 8
<9
9
> (+$ 4 5)
>(+$ 4 5)
>(+$ 3 6)
>(+$ 2 7)
>(+$ 1 8)
>(+$ 0 9)
<9
9

実行結果から, +#は再帰的プロセスを生成し, +$は反復的プロセスを生成することが分かります. +$の定義が末尾再帰的であるため, +$は反復的プロセスを生成します.

+#は, aが0でなかったとき+#を呼び出し, その結果をincの引数として与えています. このことから, +#は再帰的プロセスを生成します.

一方, +$では, aが0でなかったとき+$を呼び出しますが, その結果を使って計算する式となっていません. つまり, 末尾再帰の形をしています. よって, +$は再帰的プロセスを生成します.