SICP 問題1.30

2017/08/25

#sicp

※問題29は積分わからないのでスキップします。

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

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

ちなみに「上のsumの手続き」はこんなの。

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

sumを使った具体例として、sum-cubesをおさらいする。

(define (inc n) (+ n 1))
(define (cube x) (* x x x))

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

(define (sum-cubes a b)
  (sum cube a inc b))

(sum-cubes 1 10) を呼ぶと下記のように展開されていく。

(sum-cubes 1 10)
↓
(sum cube 1 inc b)
↓
(+ (cube 1) (sum cube (inc 1) inc b))

なるほどなるほど。

問題で提示されてる穴埋めから考えようとしたのだけど思いつかなかったので、一旦再帰的プロセスのsumから自分なりに反復的に書き直してみる。
まずは何も考えずに愚直に書いてみる。

(define (sum term a next b)
  (sum-iter term a next b 0))

(define (sum-iter term start next end result)
  (if (> start end) result
      (sum-iter term (next start) next end (+ (term start) result) )))

(print (sum cube 1 inc 10))

sum関数の中に収めてないので必要なものを全て引数で渡す必要があるため、めっちゃ無駄なこと書いてあるけどとりあえず動いたっぽい。
次にsumの中に収めて無駄を省く。

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

(print (sum cube 1 inc 10))

動いた！これで問題文に提示されたものと形はあってるっぽいので、改行とか変数名とかを合わせる。

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

できたっぽい。
traceで確認する。

(use slib)
(require 'trace)

(define (sum 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)
(print (sum cube 1 inc 10))

; CALL sum #[proc] 1 #[proc] 10
; CALL iter 1 0
;   CALL iter 2 1
;     CALL iter 3 9
;       CALL iter 4 36
;         CALL iter 5 100
;         RETN iter 3025
;       RETN iter 3025
;     RETN iter 3025
;   RETN iter 3025
; RETN iter 3025
;                              RETN sum 3025
; 3025

できたかな！