- 下記の2つの手続きを、置き換えモデルを用いて図示せよ
- そのプロセスは反復的か再帰的か?
プロセスを図示することが大切。
プロセス1
(plus 3 3) ==> (inc (plus 2 3)) ==> (inc (inc (plus 1 3))) ==> (inc (inc (inc (plus 0 3)))) ==> (inc (inc (inc 3))) ==> (inc (inc 4)) ==> (inc 5) ==> 6
プロセス2
(plus 3 3) ==> (+ 2 4) ==> (+ 1 5) ==> (+ 0 6) ==> 6
回答
; inc, dec を定義 (define (inc x) (+ x 1)) (define (dec x) (- x 1)) ; +を再定義すると動かなくなる(inc, decの定義に+を実装しているので) (define (plus a b) (if (= a 0) b (inc (plus (dec a) b)))) ;再帰的プロセスによる実装 ;数が大きいとオーバーフローしてしまう ; ;(plus 1000000 1000000) ;ERROR: Stack overflow ;ABORT: (stack-overflow) (define (plus a b) (if (= a 0) b (+ (dec a) (inc b)))) ;反復的プロセスによる実装 ;数が大きくても大丈夫 ; ;(plus 1000000 1000000) ;2000000