問題1.11

(5am:test exercise-1.11
  (5am:is (zerop (f 0)))
  (5am:is (= 2 (f 2)))
  (5am:is (= (+ (f 2)
                (* 2 (f 1))
                (* 3 (f 0)))
             (f 3))))

;; recursive
(defun f (n)
  (if (< n 3)
      n
      (+ (f (1- n))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))

;; (iter (for i below 10) (collect (f i)))
;; => (0 1 2 4 11 25 59 142 335 796)

;; f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)
;; f(3) = f(2) + 2f(1) + 3f(0)

;; 0   1   2
;; a + b + c

;; a <- b
;; b <- c
;; c <- 3a + 2b + c

;; iterative
(defun f (n)
  (if (< n 3)
      n
      (f-iter 0 1 2 n)))

(defun f-iter (a b c n)
  (if (< n 3)
      c
      (f-iter b c (+ (* 3 a) (* 2 b) c) (1- n))))