JavaScript・再帰・トランポリン

現状整理

• JavaScript では末尾再帰最適化(PTE: Proper Tail Call) は、完全には期待できない
  • https://kangax.github.io/compat-table/es6/
  • 末尾再帰による最適化 - Qiita
• なので再帰は注意して使わねばならない
  • スタックオーバーフローしないことをチェック
  • 再帰を辞めて for 文とかに何とか変換する
• とはいえ再帰を使いたい
  • こともある
  • じゃあどうするか？が本稿の目的

再帰におけるスタックオーバーフローは、末尾再帰の最適化ができる他の言語でも起こりえる(例: 末尾再帰できない場合)。じゃあ、他の言語の場合どうしているかというと、トランポリンするらしい。もちろん JavaScript でもトランポリンできる。トランポリンすると、再帰が深くなってもスタックオーバーフローしない。

処方箋

ざっくりいうと以下の処方でスタックオーバーフローしなくなる。

• 再帰関数の実装を少し変更して、終了時以外には 再帰を実行する関数(正確にはクロージャ) を返すようにする
• トランポリン関数に上記関数を渡してトランポリン化する
• トランポリン化した関数を実行する

例をあげた方がはやい。まず、スタックオーバーフローする再帰関数:

countDown.js

function countDown (num) {
  if (num === 1) return 1;
  if (num % 1000 === 0) console.log(num);
  return countDown(num - 1);
}
countDown(30000); // 18000 まではカウントダウンできた。Node v10

これを以下のように変更:

countDown2.js

function countDown2 (num) {
  if (num === 1) return 1;
  if (num % 1000 === 0) console.log(num);
  return () => countDown2(num - 1);
}

これをトランポリン関数に渡してあげる:

function trampoline (fn) {
  return (...args) => {
    let result = fn(...args);
    while (typeof result === 'function') {
      result = result();
    }
    return result;
  };
}

const tramped = trampoline(countDown2);

そんで実行

console.log(tramped(30000)); // -> カウントダウンされ、再帰の結果の 1 が返される

まあ、簡単。

何が起こっているのか？

私の説明よりも、わかりやすい説明があるのでそれを紹介

• StackOverflow
  • https://stackoverflow.com/a/27704484/9427427
  • トランポリンというファンシーな名前の由来もばっちりわかる
• Using trampolines to manage large recursive loops in JavaScript
  • https://blog.logrocket.com/using-trampolines-to-manage-large-recursive-loops-in-javascript-d8c9db095ae3

関数を実行すると関数が返ってくるので、それをまた実行するとまた関数が帰ってくるのでそれを実行して、というように(スタックに積むのではなく)同一のフレームで逐次処理ができるのがポイント。再帰を while を使ったイテレーションに変換した、ともいえる。

まとめ

JSの再帰でスタックオーバーフローするときはトランポリンしよう。