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