Kamuycikap - SentenceDataBase

日々の勉強の記録を気分で書き綴るブログ

Emacs Lisp: 再帰について

階乗を作る

再帰処理で階乗を作る

再帰の定石
●終了条件を調べ、終了なら初期値を返す
●引数に対して処理をする
●処理結果を引数として自分自身を呼び出す
(defun factorial-test (n)
  (cond
   ((zerop n) 1)
   (t (* n (factorial (1- n))))))

(factorial 4)


差が1の等差数列の和

(defun arith-prog-test (n)
  (cond
   ((zerop n) 0)
   (t (+ n (arith-prog-test (1- n))))))

(arith-prog 10)

比が2の等比数列の和
=> f(n) = 2^n + f(n - 1), f(0) = 1
終了条件がf(0) = 1で、処理が2^n + f(n - 1)なので

(defun geom-prog1-test (n)
  (cond
   ((zerop n) 1)
   (t (+ (expt 2 n) (geom-prog1-test (1- n))))))

(geom-prog1-test 3)

別の式で表現
=> f(n) = 1 + 2 x f(n - 1), f(0) = 1

(defun geom-prog2-test (n)
  (cond
   ((zerop n) 1)
   (t (+ 1 (* 2 (geom-prog2-test (1- n)))))))

(geom-prog2-test 3)


フィボナッチ数列を表現
n番目のフィボナッチ数列の値を表示する関数
終了条件が2つあります。f(1) = 1, f(2) = 1
処理部分はこれ。f(n - 1) + f(n - 2)

=> f(n) = f(n - 1) + f(n - 2), f(1) = 1, f(2) = 1

  • > 1,1,2,3,5,8,13,21,34.....
(defun fibonacci (x)
  (cond
   ((= x 1) 1)
   ((= x 2) 1)
   (t (+ (fibonacci (- x 1))
         (fibonacci (- x 2))))))

(fibonacci 5)