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

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