Emacs Lisp： 再帰の再帰

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)))

となります。