問題1.30 – SICP(計算機プログラムの構造と解釈)その13

問題1.30

線形再帰の sum 手続き

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

a から b までの整数の和(線形再帰手続き)

(define (sum-integers1 a b)
  (define (identify x) x)
  (define (inc x) (+ x 1))
  (sum1 identify a inc b))

(sum-integers1 1 10)

gosh> sum-integers1
gosh> CALL sum1 #[proc] 1 #[proc] 10
 CALL sum1 #[proc] 2 #[proc] 10
  CALL sum1 #[proc] 3 #[proc] 10
   CALL sum1 #[proc] 4 #[proc] 10
    CALL sum1 #[proc] 5 #[proc] 10
    RETN sum1 45
   RETN sum1 49
  RETN sum1 52
 RETN sum1 54
RETN sum1 55
55

a から b までの整数の3乗の和(線形再帰手続き)

(define (sum-cubes1 a b)
  (define (cube x) (* x x x))
  (define (inc x) (+ x 1))
  (sum1 cube a inc b))

(sum-cubes1 1 10)

gosh> sum-cubes1
gosh> CALL sum1 #[proc] 1 #[proc] 10
 CALL sum1 #[proc] 2 #[proc] 10
  CALL sum1 #[proc] 3 #[proc] 10
   CALL sum1 #[proc] 4 #[proc] 10
    CALL sum1 #[proc] 5 #[proc] 10
    RETN sum1 2925
   RETN sum1 2989
  RETN sum1 3016
 RETN sum1 3024
RETN sum1 3025
3025

反復的な sum 手続き(問題の答え)

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

a から b までの整数の和(反復的手続き)

(define (sum-integers2 a b)
  (define (identify x) x)
  (define (inc x) (+ x 1))
  (sum2 identify a inc b))

(sum-integers2 1 10)

gosh> sum-integers2
gosh> CALL iter 1 0
 CALL iter 2 1
  CALL iter 3 3
   CALL iter 4 6
    CALL iter 5 10
    RETN iter 55
   RETN iter 55
  RETN iter 55
 RETN iter 55
RETN iter 55
55

a から b までの整数の3乗の和(反復的手続き)

(define (sum-cubes2 a b)
  (define (cube x) (* x x x))
  (define (inc x) (+ x 1))
  (sum2 cube a inc b))

(sum-cubes2 1 10)

gosh> sum-cubes2
gosh> 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
3025
計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
«
»