Common Lisp でフィボナッチ数列（末尾再帰）

フィボナッチ数列を末尾再帰で求める。

(defun mk-list (x max)
  (if (= x max) 
      (list max)
      (cons x (mk-list (+ x 1) max))))

;; 二重再帰
(defun fib (x) 
  (cond
    ((= x 1) 1)
    ((= x 2) 1)
    (t (+ (fib (- x 1))(fib (- x 2))))))

(mapcar #'fib (mk-list 1 10))
;;=>(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

• 前回の値と前々回の値を引数にとり、加算して前回の値とする。
• 前回の値は次には前々回の値になる。
• count はループ回数を数えるためのカウンタ。

(defun fib2 (x) (fib2a 1 1 x))

;; 末尾再帰
(defun fib2a (acc b count)
  (if (= count  2)
     acc
     (fib2a (+ acc b) acc (- count 1))))

(mapcar #'fib2 (mk-list 1 10))
;;=>(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

(trace fib2)
(trace fib2a)
* (fib2 6)
  0: (FIB2 6)
    1: (FIB2A 1 1 6)
              | |
              +++
                |
      2: (FIB2A 2 1 5)
                | |
                +++
                  |
        3: (FIB2A 3 2 4)
                  | |
                  +++
                    |
          4: (FIB2A 5 3 3)
                    | |
                    +++
                      |
            5: (FIB2A 8 5 2)
            5: FIB2A returned 8
          4: FIB2A returned 8
        3: FIB2A returned 8
      2: FIB2A returned 8
    1: FIB2A returned 8
  0: FIB2 returned 8
8

二重再帰は演算回数が爆発的に増える。

(defun count-up () (setf loop-cnt (+ loop-cnt 1)))

(defun fib (x) 
  (progn
    (count-up)
    (cond
      ((= x 1) 1)
      ((= x 2) 1)
      (t (+ (fib (- x 1))(fib (- x 2)))))))

(defun fib-cnt (x) 
  (progn
    (setf loop-cnt 0)
      (list (fib x) loop-cnt)))

(mapcar #'fib-cnt (mk-list 1 20))

;;=> (フィボナッチ数 再帰回数)
    ((1 1) (1 1) (2 3) (3 5) (5 9) (8 15) (13 25) (21 41) (34 67) 
     (55 109) (89 177) (144 287) (233 465) (377 753) (610 1219) 
     (987 1973) (1597 3193) (2584 5167) (4181 8361) (6765 13529))

末尾再帰

(defun fib2 (x) (fib2a 1 1 x))

;; 末尾再帰
(defun fib2a (acc b count)
  (progn
    (count-up)
    (if (<= count  2)
       acc
       (fib2a (+ acc b) acc (- count 1)))))

(defun fib2-cnt (x) 
  (progn
    (setf loop-cnt 0)
      (list (fib2 x) loop-cnt)))

(mapcar #'fib2-cnt (mk-list 1 20))
;;=> (フィボナッチ数 再帰回数)
  ((1 1) (1 1) (2 2) (3 3) (5 4) (8 5) (13 6) (21 7) (34 8)
   (55 9) (89 10)(144 11) (233 12) (377 13) (610 14) (987 15)
   (1597 16) (2584 17)(4181 18) (6765 19))

隣り合うフィボナッチ数の比は黄金比に収束する。

(defun mk-list (x max)
  (if (= x max) 
      (list max)
      (cons x (mk-list (+ x 1) max))))


(defun fib2 (x) (fib2a 1 1 x))
;; 末尾再帰
(defun fib2a (acc b count)
  (if (<= count  2)
     acc
     (fib2a (+ acc b) acc (- count 1))))

(setf fib-list (mapcar #'fib2 (mk-list 1 30)))
;; => fib-list
;;   (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
;;    1597 2584 4181 6765 10946 17711 28657 46368 75025 
;;    121393 196418 317811 514229 832040)

(defun zip (x y acc)
  (if (or (null x)(null y))
    acc
    (zip (cdr x) (cdr y) (append acc (list (list (car x) (car y)))))))

(defun div (ls) (float (/ (cadr ls) (car ls))))

(mapcar #'div (zip fib-list (cdr fib-list) '()))
;; => 
(1.0 2.0 1.5 1.6666666 1.6 1.625 1.6153846 1.6190476 1.617647 1.6181818
 1.6179775 1.6180556 1.6180258 1.6180371 1.6180328 1.6180345 1.6180338 
 1.618034  1.618034  1.618034  1.618034  1.618034  1.618034  1.618034 1.618034
 1.618034  1.618034  1.618034  1.618034)