再帰と分割統治 — 大きい問題を小さい自分に投げる

ディレクトリの中のディレクトリを、何段でもたどりたい。組織図の下に何人ぶら下がっているか数えたい。こうした「同じ形が入れ子になっている」問題は、ループで書くと途端に面倒になります。

再帰は、この入れ子を構造のとおりに書くための道具です。そして同じ発想を「入れ子でない問題を、自分で入れ子にする」方向へ使うと、分割統治になります。

この章で学ぶこと

• 再帰を基底ケースと再帰ステップの 2 つに分けて設計する
• 再帰木を描いて、手数と深さを数える
• コールスタックが空間を食うこと。反復とどちらで書くか
• 分割統治の型と、マージソート・クイックソートの違い
• 安定ソートが要る場面

前提知識

計算量 の O 記法と、時間計算量・空間計算量の区別を前提にします。二分探索 を読んでいると、分割統治の節が早く入ります。

再帰は 2 つの部品でできている

再帰関数に要るのは 2 つだけです。

部品	役割
基底ケース	それ以上分解しない最小の入力。ここで再帰が止まる
再帰ステップ	入力を必ず小さくして自分を呼ぶ

階乗で見ます。

function factorial(n: number): number {
  if (n === 0) return 1;      // 基底ケース
  return n * factorial(n - 1); // 再帰ステップ (n が 1 減る)
}

設計で効くのは順序です。先に「どこで止まるか」を決め、次に「どう小さくするか」を決めます。逆にすると、止まらない再帰ができあがります。

止まらないとどうなるか

基底ケースを書き忘れた関数を実行すると、こうなります。

function depth(n: number): number {
  return depth(n + 1); // 基底ケースが無い。しかも n が増えている
}
depth(0);
// RangeError: Maximum call stack size exceeded

**この上限は言語仕様で決まっていません。**エンジンが積めるコールスタックの量で決まる実装依存の値です。エラーの名前もエンジンで違い、V8 と Safari は RangeError: Maximum call stack size exceeded、Firefox は InternalError: too much recursion を投げます。

Node.js で実測すると 1 万段前後で落ちました。1 フレームあたりのローカル変数が増えれば、この段数は減ります。「何段までなら安全か」を数字で覚えるのではなく、入力の大きさに比例して深くなる再帰を避ける、と考えるほうが確実です。

再帰木で手数を数える

再帰の計算量は、**呼び出しの木を描いて「段数 × 各段の仕事」**で見積もります。

フィボナッチ数列を定義どおりに書くと、こうなります。

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // 1 回の呼び出しから 2 本枝が出る
}

1 回の呼び出しから枝が 2 本出て、深さは n です。**木のノード数は指数で増えます。**呼び出し回数を数えると、増え方がはっきりします。

let calls = 0;
function fib(n: number): number {
  calls++;
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
for (const n of [10, 20, 30]) {
  calls = 0;
  fib(n);
  console.log(`fib(${n}) の呼び出し回数: ${calls}`);
}
// fib(10) の呼び出し回数: 177
// fib(20) の呼び出し回数: 21891
// fib(30) の呼び出し回数: 2692537

n が 10 増えるたびに約 123 倍です。枝分かれする再帰は指数になると覚えてかまいません。

上限は枝の本数から 2ⁿ ですが、片方の枝が 1 段浅いぶん実際はもっと緩やかで、約 1.6ⁿ です。n が 10 増えて 123 倍というのがこの 1.6 の 10 乗にあたります。上限をそのまま見積もりに使うと 400 倍ほど過大になるので、木を数えるときは枝の深さの違いまで見ます。

図で fib(3) が 2 回、fib(2) が 3 回現れています。同じ引数を何度も計算し直しているのが指数の正体です。ここに気づくのが動的計画法の入口になります。

**枝が 1 本なら指数にはなりません。**階乗も二分探索も枝は 1 本で、木は一本道です。枝の本数を先に数えてください。

コールスタックが空間を食う

再帰の呼び出しは、戻り先を覚えておくためにコールスタックへ積まれます。同時に積まれている段数が、そのまま空間計算量になります。

書き方	時間	空間
二分探索 (反復)	O(log n)	O(1)
二分探索 (再帰)	O(log n)	O(log n)

同じアルゴリズムでも空間が変わります。二分探索の章で扱ったとおり、計算量を書くときは呼び出しスタックを数え忘れないのが要点です。

深さが O(log n) なら実質問題になりません。100 万件でも 20 段です。危ないのは深さが n に比例する再帰で、これは 10 万件のリストを 1 件ずつ再帰でたどるような書き方で起きます。

分割統治 — 分ける・解く・併合する

再帰を「入れ子の構造をたどる」から一歩進めて、入れ子でない問題を自分で分割するのが分割統治です。型は 3 段です。

1. 分ける — 入力を小さな塊に切る
2. 解く — 各塊を再帰で解く
3. 併合する — 部分の答えを組み立てて全体の答えにする

二分探索はこの型の特殊な形です。半分に分けたあと、片方しか解かず、併合も要らない。だから O(log n) で済みます。

マージソート — 併合に仕事がある

分けるのは真ん中で切るだけ、仕事は併合側にあります。

function mergeSort(xs: number[]): number[] {
  if (xs.length <= 1) return xs; // 基底ケース: 1 件以下はソート済み
  const mid = Math.floor(xs.length / 2);
  const left = mergeSort(xs.slice(0, mid));
  const right = mergeSort(xs.slice(mid));
  return merge(left, right);
}

function merge(a: number[], b: number[]): number[] {
  const out: number[] = [];
  let i = 0;
  let j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) out.push(a[i++]); // 同値なら左を先に取る = 安定になる条件
    else out.push(b[j++]);
  }
  return out.concat(a.slice(i)).concat(b.slice(j));
}

console.log(mergeSort([5, 3, 8, 1, 9, 2, 7]).join(","));
// 1,2,3,5,7,8,9

計算量は段数 × 各段の仕事で出ます。半分ずつ切るので段数は log₂ n、各段では全要素をちょうど 1 回ずつ併合するので O(n)。かけて O(n log n) です。

追加のメモリは O(n) 要ります。併合のたびに新しい配列を作るからです。

クイックソート — 分けるほうに仕事がある

基準値 (ピボット) より小さい組と大きい組に分けます。併合は連結するだけです。

function quickSort(xs: number[]): number[] {
  if (xs.length <= 1) return xs;
  const pivot = xs[xs.length - 1];
  const rest = xs.slice(0, -1);
  const smaller = rest.filter((x) => x < pivot);
  const larger = rest.filter((x) => x >= pivot);
  return [...quickSort(smaller), pivot, ...quickSort(larger)];
}

console.log(quickSort([5, 3, 8, 1, 9, 2, 7]).join(","));
// 1,2,3,5,7,8,9

上のコードは読みやすさを優先した非 in-place 版です。filter とスプレッドで各段に新しい配列を作るので、追加メモリは下の表の O(log n) になりません。表の値は配列を直接入れ替える in-place 版のもので、追加メモリが再帰の深さぶんで済むのはそちらです。

ピボットの選び方で性能が決まります。毎回ちょうど半分に割れれば段数は log₂ n で O(n log n)。しかしすでにソート済みの配列に対して末尾をピボットにすると、片側が常に空になって段数が n まで伸び、O(n²) に落ちます。

	マージソート	クイックソート
時間 (平均)	O(n log n)	O(n log n)
時間 (最悪)	O(n log n)	O(n²)
追加メモリ	O(n)	O(log n) (再帰の深さ分)
安定性	安定	不安定

最悪ケースを避けたいならマージソート、メモリを使いたくないならクイックソート、という住み分けです。言語やライブラリの組み込みソートは、この 2 つのどちらかをそのまま使うより、複数の手法を組み合わせた実装になっていることが多くあります。

安定ソートが要る場面

安定 とは、比較して等しい要素の元の並び順が保たれることです。

type Row = { name: string; score: number };
const rows: Row[] = [
  { name: "a", score: 1 }, { name: "b", score: 2 }, { name: "c", score: 1 },
  { name: "d", score: 2 }, { name: "e", score: 1 },
];
const sorted = [...rows].sort((x, y) => x.score - y.score);
console.log(sorted.map((r) => r.name).join(""));
// acebd

score が 1 の 3 件は a, c, e の順で、2 の 2 件は b, d の順です。どちらも元の並びのままです。

これが効くのは複合キーで並べ替えるときです。「部署順、その中では入社日順」で並べたいなら、入社日で並べてから部署で並べると 1 回の比較関数で 2 段の順序が作れます。安定でなければ、後の並べ替えが前の並べ替えを壊します。

JavaScript の Array.prototype.sort は、ECMAScript 2019 以降、仕様で安定であることが要求されています。それ以前は処理系依存でした。

警告

比較関数を省くと、sort は要素を文字列に変換して UTF-16 コードユニット順で比べます。数値の配列で [1, 30, 4, 21, 100000].sort() が [1, 100000, 21, 30, 4] になるのはこのためです。数値を並べるなら比較関数を必ず渡します。

判断の手順

再帰と反復のどちらで書くか

状況	選ぶもの
扱うデータ自体が入れ子 (木・ディレクトリ・JSON)	再帰。構造とコードの形が一致して読みやすい
深さが入力の件数に比例する (リストを 1 件ずつ)	反復。スタックが溢れる
深さが log n に収まる (半分ずつ削る)	どちらでもよい。空間を切り詰めたいときだけ反復
枝分かれして同じ引数を何度も解く	再帰のままメモ化するか、表に置き換える

「まずソートする」と決めた時点の見積もり

手順の中に 1 回でも比較でソートする処理が入ると、全体の計算量はそこで O(n log n) に律速されます。要素どうしを比べて並べ替える方法は、どう工夫しても O(n log n) より速くならないことが分かっているからです。

例外があります。値の範囲が限られているとき — 0 から 100 の点数、日付、固定桁の ID など — は、比較せずに「値を数える」方法で O(n) に落とせます。この下界が効くのは比較で並べ替える方法だけです。

たとえば「重複を除いてから先頭 10 件を返す」を、ソートしてから隣同士を比べる方法で書くと O(n log n) です。同じことは Set を使えば O(n) でできます。計算量の章の「隠れたループに注意する」と同じ判断で、**ソートは「隠れた O(n log n)」**として数えてください。

逆に、ソートしたあとで二分探索を何度も回すなら、初回のソート代を検索回数で割って考えます。1 回しか探さないなら線形探索のほうが速いこともあります。

よくある誤解

「再帰はループより遅い」 — 呼び出しのぶんの手間はありますが、オーダーが変わるわけではありません。遅くなるのは、同じ引数を何度も解き直しているときです。それは再帰のせいではなく、重なりを潰していないせいです。

「末尾再帰なら深くしても安全」 — 末尾呼び出し最適化は ECMAScript の仕様には入っているものの、主要なエンジンで広く実装されているとは言えません。Node.js (V8) では、末尾の形で書いた再帰も同じ桁の段数で RangeError になります (実測で 7 千段前後。累算用の引数が 1 つ増えたぶん、本文の 1 万段前後より浅くなります)。深さが入力に比例する再帰は、末尾再帰にしても落ちると考えてください。

「クイックソートはマージソートより速い」 — 平均では定数倍で有利ですが、最悪 O(n²) です。ソート済みに近い入力が来る場面では逆転します。

「安定かどうかは細かい話」 — 複合キーで並べ替える処理では結果が変わります。並べ替えを 2 回に分けて書いているコードは、安定性に依存しています。

確認問題

問 1. 組織図の全員数を数える関数が、社員 5 万人のデータで RangeError を出しました。木の深さは最大 12 段です。どこを疑いますか。

答え: 木をたどる再帰ではなく、同僚のリストを 1 件ずつ再帰でたどっている箇所を疑います。

深さ 12 段でスタックが溢れることはありません。1 万段前後は積めるからです。深さ 12 の木構造をたどる再帰は、最大でも 12 段しか積まれません。

RangeError が出たということは、入力の件数に比例して深くなる再帰が別にあるということです。よくある形は次の 2 つです。

• 配列を「先頭 1 件 + 残り」に分けて自分を呼ぶ書き方。5 万件なら 5 万段になる
• 木に閉路が混ざっていて、同じノードを行き来し続けている (親を子として登録してしまった等)

切り分けは、再帰関数に現在の深さを渡して、一定を超えたら情報を出して止めることです。深さが件数に近づいていれば前者、同じノード名が繰り返し出れば後者です。

**深さは「データの形」で決まります。**件数ではありません。ここを取り違えると、木の段数を見て安全だと判断してしまいます。

問 2. 商品一覧を「カテゴリ順、同じカテゴリなら価格の安い順」で並べたい。並べ替えを 2 回に分けて書きました。どちらを先にしますか。

答え: 価格を先に、カテゴリを後にします。

安定ソートでは、後から適用した順序が外側になります。優先したいキーを最後に持ってくる、と覚えます。

const sorted = [...items]
  .sort((a, b) => a.price - b.price)            // 内側の順序
  .sort((a, b) => a.category.localeCompare(b.category)); // 外側の順序

先にカテゴリで並べると、後の価格ソートがカテゴリの並びを壊します。

**この書き方は安定性に依存しています。**比較関数を 1 つにまとめて category を先に比べ、同値なら price を比べる形にすれば、安定性に依存せず、走査も 1 回で済みます。並べ替えを 2 回に分けてよいのは、キーが動的に決まるなど、1 つの比較関数にまとめにくいときです。

問 3. 1,000 万件のレコードをマージソートで並べ替えたら、メモリが足りずに落ちました。クイックソートに変えれば解決しますか。

答え: 追加メモリは減りますが、最悪ケースの危険と引き換えです。件数がメモリに載らないなら、どちらでも解決しません。

判断を 2 段に分けます。

**1 段目 — そもそも全件がメモリに載るか。**載らないなら、ソートアルゴリズムの選択では解決しません。データを塊に分けて個別にソートし、ソート済みの塊どうしを併合する形になります。この併合は本文の merge そのもので、分割統治の「併合」だけを外に出した形です。

2 段目 — 載るなら、追加メモリの差が効くか。マージソートは併合先の配列に O(n)、クイックソートは配列を直接入れ替える in-place 版なら再帰の深さぶんで O(log n) です。1,000 万件なら差は大きく、収まる可能性があります。本文に載せたクイックソートは非 in-place 版なので、そのまま持っていくとメモリは減りません。

**ただし代償があります。**クイックソートは最悪 O(n²) です。すでにソート済みに近いデータが来る場面 — 日次で追記されるログ、主キー順に取り出したレコード — では、この最悪ケースを踏みやすくなります。ピボットをランダムに選ぶか中央値を推定すれば確率を下げられますが、保証はなくなりません。

安定性も失われます。複合キーで 2 回に分けて並べ替えているなら、結果が変わります。

まとめ

• 再帰は基底ケースと再帰ステップの 2 つ。止まる場所を先に決める
• 深さの上限は言語仕様で決まっておらず実装依存。Node.js の実測で 1 万段前後
• 計算量は再帰木の段数 × 各段の仕事で見積もる。枝が 2 本以上に分かれると指数
• **コールスタックは空間計算量に数える。**深さが件数に比例する再帰は反復で書く
• 分割統治は分ける・解く・併合する。二分探索は「片方しか解かず併合も無い」特殊形
• マージソートは最悪も O(n log n) で安定、追加メモリ O(n)。クイックソートは最悪 O(n²) で不安定、追加メモリ O(log n)
• 安定ソートは複合キーで並べ替えるときに結果を変える。優先したいキーを後に適用する
• Array.prototype.sort は ECMAScript 2019 以降、仕様で安定。比較関数を省くと文字列比較になる
• **手順に比較ソートが入ると全体が O(n log n) に律速される。**値の範囲が限られていれば比較せずに数える方法で O(n) に落とせる

関連リファレンス

• MDN — Array.prototype.sort() — ECMAScript 2019 以降は仕様で安定であること、比較関数を省いたときの UTF-16 コードユニット順
• MDN — InternalError: too much recursion — エンジンごとのエラー名と、基底ケースの欠落が原因になること
• TypeScript デザインパターン — Composite — 再帰的な構造を型で表す側の話

次に読む

• グラフと探索 — 再帰が枝分かれする代表例。訪問済みの管理が要る理由
• 動的計画法 — 再帰木に同じ引数が現れたときに何をするか
• 計算量 — 再帰木から手数を数える土台