SICP: Exercise 1.30

問題 1.30

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

(define (sum term a next b)
  (define (iter a result)
    (if ⟨??⟩
        ⟨??⟩
        (iter ⟨??⟩ ⟨??⟩)))
  (iter ⟨??⟩ ⟨??⟩))

「計算機プログラムの構造と解釈 第二版 1.3.1 引数としての手続き」より

元の sum は再帰的プロセス。

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

例えば 1〜3 の和を求めるときは、置換モデルだと以下のようになる。

(sum identity 1 inc 3)
(+ 1 (sum identity 2 inc 3))
(+ 1 (+ 2 (sum identity 3 inc 3)))
(+ 1 (+ 2 (+ 3 (sum identity 4 inc 3))))
(+ 1 (+ 2 (+ 3 0)))
(+ 1 (+ 2 3))
(+ 1 5)
6

反復的プロセスで書くと

(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
      result
      (iter (next a)
            (+ (term a) result))))
  (iter a 0))

上の例は以下の結果になる。

(sum identity 1 inc 3)
(iter 1 0)
(iter 2 1)
(iter 3 3)
(iter 4 6)
6