問題1.9~問題1.15
問題1.9
以下のように前者の式は再帰的プロセスであり、後者の式は反復的プロセスとなる。
この場合も再帰的な手続きのプロセスが、再帰的とは限らない例である。
(+ 4 5) (inc (+ 3 5)) (inc (inc (+ 2 5))) (inc (inc (inc (+ 1 5)))) (inc (inc (inc (inc (+ 0 5))))) (inc (inc (inc (inc 5)))) (inc (inc (inc 6))) (inc (inc 7)) (inc 8) 9
注 (inc (+ (dec a) b))において、(dec a)に関しての評価は行えるが、incの評価は引数が数になるまで行えない。
(+ 4 5) (+ 3 6) (+ 2 7) (+ 1 8) (+ 0 9) 9
問題1.10
(A 1 10) 1024 (A 2 4) 65536 (A 3 3) 65536
(define (f n) (A 0 n)) 2nを計算する
(define (g n) (A 1 n)) 2^nを計算する 注 必ずy=1の評価がy=0の評価よりも先に実行される
(define (h n) (A 2 n)) 2 ^ 2 ^ ... ^ 2 (n回)を計算する 注 (A 2 n) = (A 1 (A 1 (... (A 1 2)...) となる ここで(g n)の結果より (A 1 n ) = 2^n を用いて展開する
問題1.11
再帰的プロセス
(define (f n) (if (<= n 3) n (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
反復的プロセス
(define (f n) (f-iter 3 2 1 n)) (define (f-iter a b c n) (cond ((= n 3) a) ((= n 2) b) ((= n 1) c) (else (f-iter (+ a (* 2 b) (* 3 c)) a b (- n 1)))))
問題1.12
(define (pas-tri n m) (cond ((= m 1) 1) ((= m n) 1) ((< n m) 0) (else (+ (pas-tri (- n 1) (- m 1)) (pas-tri (- n 1) m)))))
問題1.13
証明問題であるため省略。
問題1.14
問題1.15
a. 3^4 = 81 < 121.5 < 3^5 = 243
よって5回
b. O(log n)