概要
再帰は美しいが、危険である。
JavaScriptでは関数呼び出しのたびにコールスタックが積まれるため、深い再帰はスタックオーバーフローを引き起こすリスクを伴う。
それでも再帰は「自己参照的構造を自然に扱う強力な手法」であり、正しく使えば強力な表現力を持つ。
本稿では、再帰処理を以下の観点で整理する：
- 単純再帰とその限界
- 末尾再帰最適化（TCO）の理論とJavaScriptの対応状況
- 反復（ループ）への変換
- メモ化による再計算回避
- 抽象化された再帰の再利用戦略
1. 単純再帰とスタックの問題
function factorial(n) {
if (n === 0) return 1;
return n * factorial(n - 1);
}
factorial(10000); // ❌ RangeError: Maximum call stack size exceeded
→ ✅ JavaScriptの再帰はスタックに依存する
2. 末尾再帰（Tail Call Optimization）とは？
function factorial(n, acc = 1) {
if (n === 0) return acc;
return factorial(n - 1, acc * n); // ✅ 最後の呼び出しでreturn
}
- ✅ 理論上は「末尾再帰」ならフレームを積まない
- ❌ ただし現状、TCOはJSエンジンで非対応（ほぼすべて）
→ ✅ 再帰の“形”は整えても、“安全性”は保証されないことに注意
3. 再帰から反復（イテレーション）への変換
function factorialIter(n) {
let result = 1;
for (let i = n; i > 0; i--) {
result *= i;
}
return result;
}
- ✅ 深さ依存なし・スタックオーバーフローなし
- ✅ パフォーマンス的にも安定
→ “深さが保証できない処理”は原則として反復で実装すべき
4. メモ化（Memoization）による計算最適化
const memo = {};
function fib(n) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
return memo[n] = fib(n - 1) + fib(n - 2);
}
- ✅ 再帰処理における重複呼び出しを防ぐ
- ✅ 特にフィボナッチや分割問題に有効
5. 汎用メモ化関数で抽象化
function memoize(fn) {
const cache = new Map();
return function (...args) {
const key = args.join(',');
if (cache.has(key)) return cache.get(key);
const result = fn(...args);
cache.set(key, result);
return result;
};
}
// 使用例
const fastFib = memoize(fib);
→ ✅ メモ化戦略を関数として再利用可能な形に抽象化
6. JSON構造などのツリー探索再帰のパターン
function traverse(obj, visit) {
for (const key in obj) {
if (typeof obj[key] === 'object') {
traverse(obj[key], visit);
} else {
visit(key, obj[key]);
}
}
}
→ ✅ 深い構造データの処理では再帰が自然
→ ✅ ただし、構造の深さ次第ではループに変換 or Stack利用も検討
7. 手動スタックによる安全な再帰変換
function traverseIter(root) {
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
process(node);
if (node.children) stack.push(...node.children.reverse());
}
}
→ ✅ 明示的スタック管理で深さを制御しつつ再帰構造を維持
設計判断フロー
① 深さが浅く保証される？ → 再帰でOK
② 深さが不定？ → ループか手動スタックで処理
③ 再帰が重い？ → メモ化で最適化
④ 末尾再帰は使える？ → ただしTCOは非対応前提
⑤ 汎用化できるか？ → 再帰 or メモ化ロジックを関数に抽象化
よくあるミスと対策
❌ 深い構造に単純再帰を適用 → スタックオーバーフロー
→ ✅ 反復 or 手動スタックに変換
❌ 再帰呼び出しで同じ計算を何度も繰り返す
→ ✅ メモ化で計算結果を使い回す
❌ データ構造と処理ロジックが密結合
→ ✅ traverse(obj, visitFn) のように分離
結語
再帰は“構造を写す力”である。
それを使いこなすには、スタックの深さと安全性を理解し、反復・メモ化・抽象化という手段を設計として選択できることが求められる。
- 再帰の魅力は“表現力”
- 限界を超えると“爆発力”
- だからこそ、選択は慎重に
再帰とは、構造の中にもう一つの構造を生む、設計者の最も美しい技術である。