JavaScript

JavaScript・再帰・トランポリン


現状整理


  • JavaScript では末尾再帰最適化(PTE: Proper Tail Call) は、完全には期待できない



  • なので再帰は注意して使わねばならない


    • スタックオーバーフローしないことをチェック

    • 再帰を辞めて 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 が返される

まあ、簡単。


何が起こっているのか?

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

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


まとめ

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