ochalog

RubyとMediaWikiとIRCが好き。

SICP: Exercise 1.9

置換モデルを使って繰り返し処理か再帰的処理かを説明せよ、という問題。

まず

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) 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

となるので、再帰的処理

次に

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

の場合

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

となるので、繰り返し処理である。