lisp 再帰ドリル

dolist もいいけど、もうちょっと lispっぽく行きたい。

そういうことなら、まずは再帰だ。そもそも体が再帰を考えることに慣れてないと自覚したので、ココを見て練習してみる。

1. まずは恒例の n! を求めるやつ。n! = 1 * 2 * 3 * ... n 。

(defun my-fact (n)
(if (= n 0)
1
(* n (my-fact (1- n)))))

;; test
(my-fact 3)
6

よし、つぎ。

2. m の n 乗を出す。m の n 乗 = m * m * m * ... m (m は n個)。

(defun my-expt (m n)
(if (= n 0) 1
(* m (my-expt m (1- n)))))

;; test
(my-expt 2 10)
1024

OK。どんどん行こう。

3. リストの要素数を求める。

(defun my-length (lst)
(if (eq lst '())
0
(1+ (my-length (cdr lst)))))

;; test
(my-length '(a b (x y z) c d))
5

ノッてきた。

4. 数値リストの要素の合計を求めるやつ。

(defun my-sum-list (lst)
(if (eq lst '())
0
(+ (car lst) (my-sum-list (cdr lst)))))

;; test
(my-sum-list '(1 2 3 4 5 6 7 8 9 10))
55

よしよし。これくらいなら行けるぞ。

5. リストから指定した要素を除いたリストを返すにはどうする?

(defun my-remove (lst e)
(if (eq lst '())
'()
(if (eq e (car lst))
(my-remove (cdr lst) e)
(cons (car lst) (my-remove (cdr lst) e)))))

;; test
(my-remove '(a x b c x x d x e f) 'x)
(a b c d e f)

･･･ちょっと苦しかったな。気を取り直して、つぎ。

6. リストの指定した要素の位置を返すやつ。 (位置はゼロ始まり)

(defun my-epos (lst e)
(if (eq lst '())
'()
(if (eq (car lst) e)
(append (my-epos (cdr lst) e) (list (1+ (length lst))))
(my-epos (cdr lst) e))))

;; test
(my-epos '(a b x c d x x e f x) 'x)
(2 5 6 9)

なんとかいけたけど結構 try and error を繰り返した。

---

まぁ、やるまえよりは再帰が身についたと思う。

今の自分にできるアプローチとしては、最初のやつ

(defun my-fact (n)
(if (= n 0) 1
(* n (my-fact (1- n)))))

を基本パターンとして書いてみて、それをちょこっと変更することを考えてみるって感じだろうか。

そんなのしなくても、慣れればズババーと書けるんだろうけど、いっぺんにそこまで到達するのは無理っぽい。

「これは再帰でいけるかな?」と考える癖だけでもつけておくことにしよう。