mahata@Choklog

問題1.30

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

(define (sum term a next b)
  (define (iter a result)
    (if <??>
        <??>
        (iter <??> <??>)))
  (iter <??> <??>))

--

再帰的な実装と反復的な実装を併せて記述する。

; --                                                                                                                          
; 標準的関数をロード                                                                                                          
; --                                                                                                                          
(load "./util.scm")

; --                                                                                                                          
; 再帰的なsumの実装                                                                                                           
; --                                                                                                                          
(define (sum-rec term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum-rec term (next a) next b)))
)

; --                                                                                                                          
; 反復的なsumの実装                                                                                                           
; --                                                                                                                          
(define (sum-rep term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)) )))
  (iter a 0)
)

(print "再帰的な計算(2): " (sum-rec cube 0 inc 2))
(print "反復的な計算(2): " (sum-rep cube 0 inc 2))
(print "再帰的な計算(3): " (sum-rec cube 0 inc 3))
(print "反復的な計算(3): " (sum-rep cube 0 inc 3))
(print "再帰的な計算(3): " (sum-rec cube 0 inc 4))
(print "反復的な計算(3): " (sum-rep cube 0 inc 4))

実行結果は次の通り。

$ gosh 1.30.scm
再帰的な計算(2): 9
反復的な計算(2): 9
再帰的な計算(3): 36
反復的な計算(3): 36
再帰的な計算(3): 100
反復的な計算(3): 100

再帰的な実装でも反復的な実装でも、同じ結果が返ることがわかる。