SICP 연습문제 1.9 ~ 1.13

;; ex 1.9
#||
(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))
in this case,
(+ 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
linear recursive

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))
 in this case,
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9
linear iterative
||#

;; ex 1.10
(define (A x y)
  (cond ((= y 0) 0)
	((= x 0) (* 2 y))
	((= y 1) 2)
	(else (A (- x 1)
		 (A x (- y 1))))))
#||
(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
...
(A 0 (A 0 (A 0 (A 0 ... (A 1 1) ... ))))
(A 0 (A 0 ... 2 ...))
(expt 2 10)

so (A 1 x) = (expt 2 x)

(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 (expt 2 2)))
(A 1 (expt 2 (expt 2 2)))
(expt 2 (expt 2 (expt 2 2)))

so (A 2 x) = 2^2^2^2^...^2 (x is # of 2)

(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (expt 2 2))

so (A 3 x) = 2^2^2^2^...^2 (# of 2 is same as 2^2^2^2^...^2 -- there are x-1 # of 2's)
||#

(define (f n) (A 0 n)) ;; returns (* 2 y)
(define (g n) (A 1 n)) ;; returns (expt 2 n)
(define (h n) (A 2 n)) ;; returns 2^2^2^...^2(# of 2's is n)

;; ex 1.11
(define (f-re n)
  (if (< n 3)
      n
      (+ (f-re (- n 1))
	 (* 2 (f-re (- n 2)))
	 (* 3 (f-re (- n 3))))))

(define (f-iter n)
  (define (iter a b c cnt)
    (cond ((< n 3) n)
	  ((= cnt n) a)
	  (else (iter (+ a (* 2 b) (* 3 c)) a b (+ cnt 1)))))
  (iter 2 1 0 2))

;; ex 1.12
(define (pascal-element row col)
  (if (or (< row 3) (= col 1) (= col row))
      1
      (+ (pascal-element (- row 1) col)
	 (pascal-element (- row 1) (- col 1)))))

exercise 1.13은 종이에 했다