Emacs Lisp: 再帰の再帰
再帰の定石(リスト入れ子バージョン) |
---|
●終了条件を調べ、終了なら初期値を返す |
●リストの先頭の要素に対して処理をする。リストの先頭の要素がリストなら、そのリストと共に自分を呼ぶ。 |
●処理結果を引数として自分自身を呼び出す |
この辺りから面白くなってきます。
以前、引数のリストの総和を計算する関数を作りました。
(defun sum (lst) (cond ((null lst) 0) (t (+ (car lst) (sum (cdr lst)))))) (sum '(1 2 3)) ;; => 6
この関数をリストのリストを取り扱えるように拡張します。
(defun sum* (lst) (cond ((null lst) 0) ((consp (car lst)) (+ (sum* (car lst)) (sum* (cdr lst)))) (t (+ (car lst) (sum* (cdr lst)))))) (sum* '(1 2 (3 4) (5))) ;; => 15
再帰関数では、まずリストの先頭の要素に対して処理を行います。
要素が「アトム」か「空ではないリスト」かで処理を分岐させます。
(consp (car lst)
ですね。
この条件が成り立つとき、リストの先頭の要素はリストです。
なので、定石に従って、自分自身を内側のリストと共に呼び出します。
(+ (sum* (car lst)) (sum* (cdr lst)))
こうなります。
条件が成り立たない時は、リストの先頭要素はリストではないので
(+ (car lst) (sum* (cdr lst)))
となります。