猫型エンジニアのブログ

プログラム/ネットワーク系の技術関連をまとめたページです 

問題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)