[SICP] 問題 1.30 : 反復的プロセスを生成する総和

上のsumの手続きは線形再帰を生成する. 総和が反復的に実行出来るように手続きを書き直せる. 次の定義の欠けているところを補ってこれを示せ:

(define (sum term a next b)
  (define (iter a result)
    (if ＜??＞
        ＜??＞
        (iter ＜??＞ ＜??＞)))
  (iter ＜??＞ ＜??＞))

総和を求める手続きが反復的プロセスを生成するように修正します. 内部手続iterの引数resultに計算の途中経過を蓄積するようにします. 手続きの定義は次のようになります.

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

(define (cube x) (* x x x))

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

;; 再帰的プロセスを生成
(define (sum-r term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum-r term (next a) next b))))

;; 反復的プロセスを生成
(define (sum-i term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ (term a) result))))
  (trace iter) ;; 内部手続きをトレースする.
  (iter a 0))

(trace sum-r)

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (sum-r identity 1 inc 10)
>(sum-r #<procedure:identity> 1 #<procedure:inc> 10)
> (sum-r #<procedure:identity> 2 #<procedure:inc> 10)
> >(sum-r #<procedure:identity> 3 #<procedure:inc> 10)
> > (sum-r #<procedure:identity> 4 #<procedure:inc> 10)
> > >(sum-r #<procedure:identity> 5 #<procedure:inc> 10)
> > > (sum-r #<procedure:identity> 6 #<procedure:inc> 10)
> > > >(sum-r #<procedure:identity> 7 #<procedure:inc> 10)
> > > > (sum-r #<procedure:identity> 8 #<procedure:inc> 10)
> > > > >(sum-r #<procedure:identity> 9 #<procedure:inc> 10)
> > > > > (sum-r #<procedure:identity> 10 #<procedure:inc> 10)
> > > >[10] (sum-r #<procedure:identity> 11 #<procedure:inc> 10)
< < < <[10] 0
< < < < < 10
< < < < <19
< < < < 27
< < < <34
< < < 40
< < <45
< < 49
< <52
< 54
<55
55
> (sum identity 1 inc 10)
>(iter 1 0)
>(iter 2 1)
>(iter 3 3)
>(iter 4 6)
>(iter 5 10)
>(iter 6 15)
>(iter 7 21)
>(iter 8 28)
>(iter 9 36)
>(iter 10 45)
>(iter 11 55)
<55
55
> 

トレースの結果からも反復的プロセスを生成していることが分かります.