概要

再帰は美しいが、危険である。
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) のように分離

結語

再帰は“構造を写す力”である。
それを使いこなすには、スタックの深さと安全性を理解し、反復・メモ化・抽象化という手段を設計として選択できることが求められる。

再帰の魅力は“表現力”
限界を超えると“爆発力”
だからこそ、選択は慎重に

再帰とは、構造の中にもう一つの構造を生む、設計者の最も美しい技術である。