Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

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の再帰でスタックオーバーフローするときはトランポリンしよう。

41semicolon
低燃費FIRE。論理・計算関連のトピックに興味があります。JavaScript,Python,Rust,F#,Coq
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away