JavaScript | 再帰とループの性能比較

JavaScript

2025.11.01

では「再帰を安全に使う工夫」について解説します。性能比較で見たように、再帰は便利だけど「深すぎる呼び出し」でスタックオーバーフローを起こす危険があります。そこで登場するのが 末尾再帰最適化 や トランポリン手法 です。

再帰を安全に使う工夫
✅ まとめ

再帰を安全に使う工夫

1. 末尾再帰（Tail Recursion）

定義: 関数の「最後の処理」が再帰呼び出しになっている形。
一部の言語（Scheme, Scala, Rustなど）では「末尾再帰最適化」が働き、ループと同じ効率で実行できる。
残念ながら JavaScriptは標準で末尾再帰最適化を保証していない ので、深すぎる再帰は危険。

例（末尾再帰版の階乗）

function factorialTail(n, acc = 1) {
  if (n === 0) return acc;          // 終了条件
  return factorialTail(n - 1, n * acc); // 最後に再帰呼び出し
}

console.log(factorialTail(5)); // 120

function factorialTail(n, acc = 1) {
  if (n === 0) return acc;          // 終了条件
  return factorialTail(n - 1, n * acc); // 最後に再帰呼び出し
}

console.log(factorialTail(5)); // 120

JavaScript

👉 acc（累積値）を引数で持ち回ることで、戻りながら計算する必要がなくなる。
👉 ただしJSでは最適化されないので、深すぎるとやはり危険。

2. トランポリン手法（Trampoline）

考え方: 再帰関数が「次に呼ぶ関数」を返すようにして、実際の呼び出しはループで行う。
こうすると「関数呼び出しの深さ」が1で固定され、スタックオーバーフローを防げる。

例（トランポリン化した階乗）

function factorialStep(n, acc = 1) {
  if (n === 0) return acc;
  return () => factorialStep(n - 1, n * acc); // 関数を返す
}

function trampoline(fn) {
  while (typeof fn === "function") {
    fn = fn();
  }
  return fn;
}

console.log(trampoline(() => factorialStep(100000))); 
// 大きな数でもスタックオーバーフローしない

function factorialStep(n, acc = 1) {
  if (n === 0) return acc;
  return () => factorialStep(n - 1, n * acc); // 関数を返す
}

function trampoline(fn) {
  while (typeof fn === "function") {
    fn = fn();
  }
  return fn;
}

console.log(trampoline(() => factorialStep(100000))); 
// 大きな数でもスタックオーバーフローしない