概要
再帰とは、自己参照的に問題を解くアルゴリズム設計である。
単なるループの代替手段ではなく、以下のような場面で絶大な威力を発揮する：
- 再帰的データ構造（ツリー・グラフ・ネスト）
- 分割統治アルゴリズム（クイックソートなど）
- 動的計画法（DP）
- メモ化によるパフォーマンス改善
- 探索系アルゴリズム（DFS/BFS/バックトラック）
本記事では、JavaScriptでの再帰設計をパターンベースで整理し、安全性・最適性・保守性を両立する戦略を構築する。
1. 基本的な再帰構造
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
factorial(5); // 120
- ✅ ベースケース（終了条件）を必ず設定
- ✅ 漸進的に問題を小さくする構造
2. 末尾再帰（Tail Recursion）
function factorialTail(n, acc = 1) {
if (n <= 1) return acc;
return factorialTail(n - 1, acc * n);
}
✅ 特徴
- 計算結果をそのまま返す構文 → 末尾再帰
- 理論的にはスタックを消費しない
- ❌ JavaScriptでは公式に最適化されていない（2025現在）
→ 大規模な末尾再帰はスタックオーバーフローを引き起こす可能性あり
3. メモ化による高速化（Memoization）
function fibMemo() {
const cache = {};
return function f(n) {
if (n <= 1) return n;
if (cache[n]) return cache[n];
return cache[n] = f(n - 1) + f(n - 2);
};
}
const fib = fibMemo();
fib(40); // 高速計算
- ✅ 重複計算を排除
- ✅ 動的計画法（DP）との相性が良い
- ✅ 一度計算した結果を保持して再利用する設計
4. 分割統治の設計：クイックソート実装
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0];
const left = arr.slice(1).filter(x => x < pivot);
const right = arr.slice(1).filter(x => x >= pivot);
return [...quickSort(left), pivot, ...quickSort(right)];
}
- ✅ 再帰的にデータを分割して解く → 分割統治法
- ❌ メモリ効率は非効率（slice/filterによるコピー）
- ✅ 関数型設計との親和性が高い
5. 再帰的データ構造の探索（ツリー）
function walkTree(node) {
console.log(node.value);
for (const child of node.children) {
walkTree(child);
}
}
- ✅ ネスト構造を処理する王道パターン
- ✅ 再帰以外では冗長になりがち
再帰処理の設計判断フロー
① データ構造がツリー状か？ → 再帰で走査
② 部分問題に分割して解けるか？ → 分割統治
③ 重複計算があるか？ → メモ化を導入
④ 再帰が深すぎてスタック限界に近い？ → ループ or Stackで置き換える
⑤ 計算の末尾で再帰している？ → 末尾再帰化して安全化（ただし最適化は期待できない）
よくある落とし穴
❌ 無限再帰（終了条件の欠落）
function recurse() {
return recurse(); // ❌ StackOverflow
}
→ 🔧 常に「ベースケース」と「縮小構造」を明確に
❌ スタックオーバーフロー（深すぎる再帰）
function count(n) {
if (n === 0) return;
count(n - 1);
}
count(100_000); // ❌ RangeError
→ 🔧 代替策：ループ / 自作スタック / setTimeoutによる分割実行
結語
再帰とは、「構造の中に構造がある問題を、その構造のまま解く方法」である。
そしてそれは、単なる構文ではなく、問題そのものの再定義でもある。
- 末尾再帰：構文的安全性
- メモ化：計算の最適性
- 分割統治：設計の抽象性
- スタック管理：実装の現実性
設計された再帰は、あらゆる複雑さを最小構成に還元する。
それこそが、再帰の本質である。