1.2.2木構造再帰、問題1.11 – SICP（計算機プログラムの構造と解釈）その5
2008年11月11日
1.2.2 木構造再帰
木構造再帰的プロセスの (fib n)。
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
(fib 4)
(+ (fib (- 4 1)) (fib (- 4 2)))
(+ (fib 3) (fib 2))
(+ (+ (fib (- 3 1)) (fib (- 3 2))) (+ (fib (- 2 1)) (fib (- 2 2))))
(+ (+ (fib 2) (fib 1)) (+ (fib 1) (fib 0)))
(+ (+ (+ (fib (- 2 1)) (fib (- 2 2))) 1) (+ 1 0))
(+ (+ (+ (fib 1) (fib 0)) 1) (+ 1 0))
(+ (+ (+ 1 0) 1) 1)
(+ (+ 1 1) 1)
(+ 2 1)
3
反復的プロセスの (fib n)。
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
(fib 4)
(fib-iter 1 0 4)
(fib-iter (+ 1 0) 1 (- 4 1))
(fib-iter 1 1 3)
(fib-iter (+ 1 1) 1 (- 3 1))
(fib-iter 2 1 2)
(fib-iter (+ 2 1) 2 (- 2 1))
(fib-iter 3 2 1)
(fib-iter (+ 3 2) 3 (- 1 1))
(fib-iter 5 3 0)
3
問題1.11
再帰的プロセスの (f n)。
再帰的プロセスの方は、計算式をそのままコードにすればよい。
(define (f n)
(if (< n 3)
n
(+ (f (- n 1))
(* 2 (f (- n 2)))
(* 3 (f (- n 3))))))
(f 4)
(+ (f 3) (* 2 (f 2)) (* 3 (f 1)))
(+ (+ (f 2) (* 2 (f 1)) (* 3 (f 0))) (* 2 2) (* 3 1))
(+ (+ 2 (* 2 1) (* 3 0)) 4 3)
(+ (+ 2 2 0) 4 3)
(+ 4 4 3)
11
反復的プロセスの (f n)。
f-iter の再帰部分では、この時点での計算結果(+ a (* 2 b) (* 3 c)) と、次のステップでの計算に必要な a と b （※c は必要ない）と、デクリメントしたカウンタ (- n 1) を引数として渡している。
(define (f n)
(if (< n 3)
n
(f-iter 2 1 0 n)))
(define (f-iter a b c n)
(if (= n 2)
a
(f-iter (+ a (* 2 b) (* 3 c)) a b (- n 1))))
(f 4)
(f-iter 2 1 0 4)
(f-iter (+ 2 (* 2 1) (* 3 0)) 2 1 3)
(f-iter (+ 2 2 0) 2 1 3)
(f-iter 4 2 1 3)
(f-iter (+ 4 (* 2 2) (* 3 1) 4 2 2))
(f-iter (+ 4 4 3) 4 2 2)
(f-iter 11 4 2 2)
11
計算機プログラムの構造と解釈
posted with amazlet at 08.11.07
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
ピアソンエデュケーション
売り上げランキング: 6542