リスト遊び 4-2 数列

リスト遊び 4-1 階乗 - by shigemk2

再帰の定石

• 終了条件を調べ、終了なら初期値を返す
• 引数に対して仕事をする
• 変化させた引数と共に自分自身を呼び出す

今回は数列をlispで表現する。

ƒ(n) = n + ƒ(n - 1), ƒ(0) = 0

(defun arith-prog (n)
  (cond
   ((zerop n) 0)
   (t (+ n (arith-prog (1- n))))))
=>arith-prog
(arith-prog 5)
15
(arith-prog 100)
5050

ƒ(n) = 2^n + ƒ(n - 1), ƒ(0) = 0

(defun geom-prog (n)
  (cond
   ((zerop n) 1)
   (t (+ (expt 2 n) (geom-prog (1- n))))))
geom-prog
(geom-prog 2)
7
(geom-prog 3)
15

(defun geom-prog1 (n)
  (cond
   ((zerop n) 1)
   (t (+ 1 (* 2 (geom-prog1 (1- n)))))))
geom-prog1
(geom-prog1 5)
63
(geom-prog1 0)
1
(geom-prog1 1)
3
(geom-prog1 2)
7
(geom-prog1 3)
15

リスト遊び―Emacsで学ぶLispの世界 (ASCII SOFTWARE SCIENCE Language)