- Common Lispで再帰関数を書くときは、
labelsでローカル関数recを定義し、condで場合分けするイディオムに統一する。 - 線形再帰は戻りがけに値を積み、末尾再帰はアキュムレータ
accに先に演算してから再帰することでスタックを節約する。 - 全列挙は「選ぶ・選ばない」の二分岐を
appendでつなぐパターンで、部分列・順列・組み合わせすべてに共通する。 - 木構造の再帰は
condのケースが3つになり、先頭がリストならcarとcdrの両方へ再帰する。
1. 再帰のイディオム（labels … cond）
Common Lispで再帰は、condで場合分けをして、関数を呼び出します。
フィボナッチ数列の定義、A0 = A1 = 1 で、An = A(n-1) + A(n-2) を、そのまま関数定義に使えます。
(defun fib (n)
(cond
((<= n 1) 1)
(t (+ (fib (- n 1))
(fib (- n 2))))))Code language: Lisp (lisp)この書き方はシンプルなのですが、再帰の定番の書き方として、labels + cond を組み合わせる方法があります。
(defun 関数名 (引数)
(labels ((rec (引数)
(cond
((基底ケース) 基底の値)
(t (rec 小さい入力)))))
(rec 引数))) ; ここで起動Code language: Lisp (lisp)この方法の特徴は、外部に公開する関数名とは別に、内部の再帰関数を作り、呼び出すパターンです。
再帰関数名としては rec （recursive）がよく使われます。
- 基底：n が 0, 1 なら 0
- 再帰：n-1項 と n-2項 を足す
(defun fib/label (n)
(labels ((rec (n)
(cond
((<= n 1) 1)
(t (+ (rec (- n 1))
(rec (- n 2)))))))
(rec n)))Code language: Lisp (lisp)このように再帰は書き換えられます。
1.1. 再帰関数と状態変数
ただ、再帰関数recを呼ぶだけでは、入れ子が複雑になっただけです。
再帰関数を分けるメリットは、引数として状態変数を渡しやすくなること。
たとえば、fib/abでは、直前2項を再帰関数に渡すと、重複する計算を減らせます。
- 基底：n が 0 なら a（a と b で直前2項を持ち歩く）
- 再帰：a を b に、b を a+b に更新しながら n を減らす
(defun fib/ab (n)
(labels ((rec (n a b)
(cond
((= n 0) a)
(t (rec (1- n) b (+ a b))))))
(rec n 0 1)))
(fib/ab 30)
;=> 832040Code language: Lisp (lisp)再帰を設計するときの思考の順番はこうです。
- 基底ケースを決める（最小の入力への答え）
- 入力をどう小さくするか決める
- 「小さい問題の答えが手元にあるとして、それをどう使えば元の問題が解けるか」を考える
3番目が核心です。(rec 小さい入力) の結果を信頼して使うと決めてから、その結果に何を足すか・何を付けるかだけを考えます。
実装する前に「もし小さい問題が解けているとしたら」と仮定して設計する習慣が、再帰を自然に書けるようになる鍵です。
| 段階 | 基底ケース | 問題を小さくする方法 | 結果の使い方 |
|---|---|---|---|
| 線形・数値 | 0 や 1 | (cdr lst) や (floor n 10) | 数値演算して戻りがけに足す |
| 線形・リスト | '() | (cdr lst) | cons で先頭に積む |
| 末尾再帰 | acc | (cdr lst) や (1- n) | acc に先に演算して渡す |
| 二分岐 | ("") など | (subseq s 1) | append（選ばない＋選ぶ） |
| 木構造 | '() や 0 | (cdr lst) | 先頭がリストなら (car) にも再帰 |
| 分割統治 | 要素数 ≤ 1 | 前半/後半に分割 | 2つの結果をマージ |
2. 第1段階：線形再帰
もっともかんたんなパターンは、線形再帰です。
基底ケースは数値（0、1 など）で、再帰ケースは数値演算して戻りがけに足す形です。
2.1. digit-sum：桁の合計
- 基底：1桁の数はそのまま桁の合計
- 再帰：末尾の桁（n mod 10）を足して、残りの桁（n / 10）に再帰する
(defun digit-sum (n)
(labels ((rec (n)
(cond
((< n 10) n)
(t (+ (mod n 10)
(rec (floor n 10)))))))
(rec n)))
(digit-sum 123)
;=> 6Code language: Lisp (lisp)2.2. list-product：リストの積
- 基底：空リストの積は 1（乗算の単位元）
- 再帰：先頭と残りの積を掛ける
(defun list-product (lst)
(labels ((rec (lst)
(cond
((null lst) 1)
(t (* (car lst)
(rec (cdr lst)))))))
(rec lst)))
(list-product '(1 2 3 4 5))
;=> 120Code language: Lisp (lisp)2.3. リストの隣接重複を除く
線形再帰で、値ではなくリストを構築することもできます。
基底ケースの戻り値が数値から '() に変わり、再帰ケースでは cons や append でつなぎます。
- 基底：空リスト、または要素が1つならそのまま
- 再帰：先頭と次の要素が同じなら先頭を捨てて再帰、違うなら先頭を残して再帰
(defun remove-consecutive-duplicates (lst)
(labels ((rec (lst)
(cond
((null lst) '())
((null (cdr lst)) lst)
((equal (car lst) (cadr lst))
(rec (cdr lst)))
(t (cons (car lst) (rec (cdr lst)))))))
(rec lst)))
(remove-consecutive-duplicates '(1 1 2 2 3 3 3))
;=> (1 2 3)Code language: Lisp (lisp)2.4. to-base：n進数変換
- 基底：0 は空リスト（桁がない）
- 再帰：末尾の桁（n mod base）を append で付け、残りの桁（n / base）に再帰する
(defun to-base (n base)
(labels ((rec (n)
(cond
((= n 0) '())
(t (append (rec (floor n base))
(list (mod n base)))))))
(rec n)))
(to-base 10 2)
;=> (1 0 1 0)
(to-base 1234 10)
;=> (1 2 3 4)Code language: Lisp (lisp)最下位である 1の位から計算されるので、1要素のリストにしたから、appendで最後尾に追加しています。
(cons (rec ...) (mod n base) などとしたいところですが、一般的なリスト（proper-list）ではなくなってしまいます。
リストの末尾は数値ではなく、リストかnilである必要があります。
あるいは、consで生成してから、最後にnreverseで反転させる方法もあります。
2.5. 相互再帰
labels に複数の関数を並べると、互いに呼び合う相互再帰が書けます。
通常の labels は rec が1つで自分自身を呼びますが、相互再帰は labels に複数の関数を置いて互いに呼び合います。
関数が状態を表します。
数字と英字が交互に現れるか検証する
alternating-p は状態ごとに違う条件を持つ状態機械です。
- 基底：文字列が空になれば検証成功（
t） - 再帰：期待する文字種が来たら次の状態へ、来なければ失敗（
nil）
(defun alternating-p (s)
(labels ((digit-turn (s)
(cond
((zerop (length s)) t)
((digit-char-p (char s 0))
(alpha-turn (subseq s 1)))
(t nil)))
(alpha-turn (s)
(cond
((zerop (length s)) t)
((alpha-char-p (char s 0))
(digit-turn (subseq s 1)))
(t nil))))
(digit-turn s)))
(alternating-p "1a2b3c")
;=> TCode language: Lisp (lisp)3. 第2段階：状態変数で末尾再帰へ変形する
線形再帰は、戻りがけに処理が残るためスタックを使います。
そこで、蓄積変数 acc （accumlator）を rec に追加して、先に処理してから再帰するのが定石です。
SBCLでは末尾呼び出しを最適化されるので、呼び出しが深くなりません。
3.1. split-string：文字列を区切り文字で分割
蓄積変数を使うパターンでは、一つ頭を切替える必要があります。
基底ケースは、先頭ではなく処理がすべて終わった最後の状態ということです。
- 基底：文字列が空なら、 acc を nreverse して返す
- 再帰：区切り文字に達したら、現在のトークンを acc に積んで続ける、
そうでなければ、トークンに1文字追加して続ける
(defun split-string (s delim)
(labels ((rec (i token acc)
(cond
((= i (length s))
(nreverse (cons token acc)))
((char= (char s i) delim)
(rec (1+ i) "" (cons token acc)))
(t
(rec (1+ i)
(concatenate 'string token
(string (char s i)))
acc)))))
(rec 0 "" '())))
(split-string "hello world foo" #\space)
;=> ("hello" "world" "foo")Code language: Lisp (lisp)線形再帰との差分：rec の引数が (n) から (n a b) や (i token acc) に変わります。
基底ケースは固定値ではなく acc をそのまま返し、再帰ケースは (演算 (rec ...)) ではなく (rec ... (演算 acc)) になります。
起動も (rec n) から (rec n 0 1) や (rec 0 "" '()) のように初期値を渡す形になります。
3.2. run-length-encode：ランレングス符号化
- 基底：空リストは空リスト
- 再帰：先頭と同じ要素が続く間を数え、
(個数 値)のペアを cons で付けて残りに再帰する - rest ; まだ見ていない残り
- current ; 現在連続している値
- count ; current が何個続いているか
- acc ; 確定済みの結果
(defun run-length-encode (lst)
(labels ((rec (rest current count acc)
(cond
((null rest)
(reverse (cons (list count current) acc)))
((equal (car rest) current)
(rec (cdr rest) current (1+ count) acc))
(t
(rec (cdr rest)
(car rest)
1
(cons (list count current) acc))))))
(if (null lst)
'()
(rec (cdr lst) (car lst) 1 '()))))
(run-length-encode '(a a a b b c))
;; => ((3 A) (2 B) (1 C))Code language: Lisp (lisp)3.3. balanced-p：括弧の対応を確認する
balanced-p は相互再帰ではなく深さを acc で持つ末尾再帰で、状態が連続値（深さ）のときはアキュムレータの方が自然です。
- 基底：深さが負なら失敗（閉じ過ぎ）、空文字列で深さ 0 なら成功
- 再帰：
(なら深さを増やす、)なら深さを減らす、それ以外はそのまま進む
(defun balanced-p (s)
(labels ((rec (s depth)
(cond
((< depth 0) nil)
((zerop (length s)) (= depth 0))
((char= (char s 0) #\()
(rec (subseq s 1) (1+ depth)))
((char= (char s 0) #\))
(rec (subseq s 1) (1- depth)))
(t
(rec (subseq s 1) depth)))))
(rec s 0)))
(balanced-p "(()())")
;=> TCode language: Lisp (lisp)4. 第3段階：全列挙 — 部分列・順列・組み合わせ
4.1. 組み合わせの列挙（append + loop … in rec ）
n ビットの全パターンなど、組み合わせパターンをすべて列挙するときには、append + loop ... in (rec ...)を使います。
(let ((rest (rec (- n 1)))) ; n-1 ビットの部分問題
(append
(loop for p in rest
collect (cons 0 p)) ; 0 を付けたもの
(loop for p in rest
collect (cons 1 p))))Code language: Lisp (lisp)- 先に残りからでできるパターン
(rec (- n 1))を求めて、 - それぞれの
loop ... collectで、新しいリストを作り、 appendで連結します。
いくつかの loop ... in restで展開して append で合わせる。
この形が全列挙の基本イディオムです。
4.2. ビットパターン
- 基底：0 ビットのパターンは空リスト 1 つだけ
- 再帰：残りの各パターンの先頭に 0 を付けたものと
1 を付けたもの、それぞれを合わせる
(defun bit-patterns (n)
(labels ((rec (n)
(cond
((= n 0) (list '()))
(t
(let ((rest (rec (- n 1)))) ; n-1 ビットの部分問題
(append
(loop for p in rest
collect (cons 0 p)) ; 0 を付けたもの
(loop for p in rest
collect (cons 1 p)))))))) ; 1 を付けたもの
(rec n)))
(bit-patterns 3)
;=> ((0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1))Code language: Lisp (lisp)線形再帰との差分：再帰ケースが1回の再帰から、rest を使った2通りの操作と append に変わります。rest = (rec 残り) を1回だけ計算して、選ばない側はそのまま、選ぶ側は何かを付けて、両方を append で合わせる形です。
4.3. subsequences：文字列の部分列を全列挙する
- 基底：空文字列の部分列は
""だけ - 再帰：残りの全部分列をそのまま使う（選ばない）か、
先頭文字を付けるか（選ぶ）、を加える
(defun subsequences (s)
(labels ((rec (s)
(cond
((zerop (length s)) (list ""))
(t (let ((rest (rec (subseq s 1))))
(append
rest
(loop for sub in rest
collect (concatenate 'string
(subseq s 0 1) sub))))))))
(rec s)))
(subsequences "abc")
;=> ("" "c" "b" "bc" "a" "ac" "ab" "abc")
(subsequences "abc")
;=> ("" "c" "b" "bc" "a" "ac" "ab" "abc")Code language: Lisp (lisp)4.4. combinations：リストから k 個選ぶ組み合わせを全列挙する
- 基底：k が 0 なら空リスト1つ。リストが空なら空
- 再帰：先頭を選ぶ（残りから k-1 個）か、
選ばない（残りから k 個）か、の二分岐をつなぐ
(defun combinations (lst k)
(labels ((rec (lst k)
(cond
((= k 0) (list '()))
((null lst) '())
(t
(let ((with (rec (cdr lst) (1- k)))
(without (rec (cdr lst) k)))
(append
(loop for c in with
collect (cons (car lst) c))
without))))))
(rec lst k)))
(combinations '(1 2 3 4) 2)
;=> ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))Code language: Lisp (lisp)4.5. permutations：リストの順列を全列挙する
- 基底：空リストの順列は空リスト1つだけ
- 再帰：要素を1つ選び、残りの順列から取り除いて先頭に付ける、というのをつなぐ
(defun permutations (lst)
(labels ((remove-one (x lst)
(cond
((null lst) '())
((equal x (car lst)) (cdr lst))
(t (cons (car lst) (remove-one x (cdr lst))))))
(rec (lst)
(cond
((null lst) (list '()))
(t
(loop for x in lst
append
(loop for p in (rec (remove-one x lst))
collect (cons x p)))))))
(rec lst)))
(permutations '(1 2 3))
;=> ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))Code language: Lisp (lisp)ここでは、外側のloopで要素を一つずつ x として分岐し、それをつないでいます。
内側の(loopr ... (rec ...))では、1つ減らしたリストで再帰しています。
5. 第4段階：木構造の再帰
データ構造が入れ子になっているとき、cond のケースが3つになります。
空なら基底の値を返し、
先頭がリストなら先頭にも残りにも再帰し（2方向）、
先頭がアトムなら先頭を処理して残りに再帰します（1方向）。
5.1. depth：S式の深さ
- 基底：空リストの深さは 0
- 再帰：先頭がリストなら
(1 + 先頭の深さ)と残りの深さの大きい方、アトムなら残りの深さ
(defun depth (lst)
(labels ((rec (lst)
(cond
((null lst) 0)
((listp (car lst))
(max (1+ (rec (car lst)))
(rec (cdr lst))))
(t (rec (cdr lst))))))
(rec lst)))
(depth '(1 (2 3) (4 (5 6))))
;=> 2Code language: Lisp (lisp)5.2. tree-filter：条件を満たすアトムをすべて集める
- 基底：空リストは空
- 再帰：先頭がリストなら、中を再帰して残りと
append、
アトムで条件を満たすなら、cons、
満たさないなら、捨てる
(defun tree-filter (pred lst)
(labels ((rec (lst)
(cond
((null lst) '())
((listp (car lst))
(append (rec (car lst))
(rec (cdr lst))))
((funcall pred (car lst))
(cons (car lst) (rec (cdr lst))))
(t (rec (cdr lst))))))
(rec lst)))
(tree-filter #'evenp '(1 (2 3) (4 (5 6))))
;=> (2 4 6)Code language: Lisp (lisp)5.3. merge-sort：マージソート
マージソートは、分割統治の典型です。
リストを半分に分けて再帰的にソートし、マージします。
- 基底：空リストまたは要素が1つならそのまま（すでにソート済み）
- 再帰：前半と後半に分けてそれぞれソートし、マージする
(defun merge-sort (lst)
(labels ((merge-two (a b)
(cond
((null a) b)
((null b) a)
((<= (car a) (car b))
(cons (car a) (merge-two (cdr a) b)))
(t
(cons (car b) (merge-two a (cdr b))))))
(rec (lst)
(cond
((null lst) '())
((null (cdr lst)) lst)
(t (let* ((mid (floor (length lst) 2))
(left (subseq lst 0 mid))
(right (subseq lst mid)))
(merge-two (rec left) (rec right)))))))
(rec lst)))
(merge-sort '(3 1 4 1 5 9 2 6 5 3))
;=> (1 1 2 3 3 4 5 5 6 9)Code language: Lisp (lisp)merge-twoは、２つのリストから小さなものを順番に取って、つなぎます。