SICPを読む_(6)1章_手続きによる抽象の構築(p21)

なんだかんだで少しずつ進んでるので、自分を褒めてあげたい今日このごろ。
ということで、今日も今日とて少しずつSICP読み進めますよ！！＞＜

問題1.9(p20)

(define (plus a b)
  (if (= a 0)
      b
      (inc (plus (dec a) b))))

(define (plus a b)
  (if (= a 0)
      b
      (plus (dec a) (inc b))))

(plus 4 5)

前者が再帰的プロセスで、後者が反復的プロセスですね。
まぁこのあたりはそこまで悩むほどでもないかとー。

問題1.10(p20)

まさか福岡Ruby会議でLT材料に使ったアッカーマン関数にここでまた出会うとは思わなかった。。。

(define (A x y)
  (cond
   ((zero? y) 0)
   ((zero? x) (* 2 y))
   ((eq? y 1) 2)
   (else
    (A (- x 1)
       (A x (- y 1))))))

(define (f n) (A 0 n))
(define (h n) (A 2 n))
(define (g n) (A 1 n))

;; 次の式の値は何かという問はこれでok
(A 1 10) ;;=>1024
(A 2 4)  ;;=>65536
(A 3 3)  ;;=>65536

最後だけ結構悩みました。
とりあえず、1つずつ試していくのも馬鹿らしかったので、法則性を見つけるために5から0までの数字をnにいれるような手続きを書きましたよっと。

(define (check x)
  (define (check-iter n)
    (cond
     ((zero? n) (cons (x n) ()))
     (else
      (cons (x n) (check-iter (- n 1))))))
  (check-iter 5))

(check f);;=>(10 8 6 4 2 0)
(check g);;=>(32 16 8 4 2 0)
(check h);;=>(~~56736 65536 16 4 2 0)

ということで
f=2n,g=2^n
最後hは数列として表せるらしい;参考
F_0 = 0, F_1 = 2
F_n = (F_(n-1))^2

ということで、問題解いてたら1時半になってたので、続きはまた明日(?)