概要

再帰とは、自己参照的に問題を解くアルゴリズム設計である。
単なるループの代替手段ではなく、以下のような場面で絶大な威力を発揮する：

再帰的データ構造（ツリー・グラフ・ネスト）
分割統治アルゴリズム（クイックソートなど）
動的計画法（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による分割実行

結語

再帰とは、「構造の中に構造がある問題を、その構造のまま解く方法」である。
そしてそれは、単なる構文ではなく、問題そのものの再定義でもある。

末尾再帰：構文的安全性
メモ化：計算の最適性
分割統治：設計の抽象性
スタック管理：実装の現実性

設計された再帰は、あらゆる複雑さを最小構成に還元する。
それこそが、再帰の本質である。