JavaScriptでスタックオーバーフローを起こさない方法

JavaScript

結論を先に述べると、setTimeOutを使って、処理をイベントキューにぶち込んでやれば良い。

どーしてそーなんの？

まず、例として普通に再帰関数を書いてみる。consle.timeとconsole.timeEndによる時間計測付き。

function countdown(n) {
  if (n === 0) {
    console.log("done");
    console.timeEnd('countdown time');
  } else {
    countdown(n - 1);
  }
}

console.time('countdown time');
countdown(10000);
// 出力
// done
// countdown time: 4ms

nが10,000なら、4msでちゃんと終了する。

一方、nが100,000だと、スタックオーバーフローが起きる。ちなみに、ローカルのnode.jsで実験中。

function countdown(n) {
  if (n === 0) {
    console.log("done");
    console.timeEnd('countdown time');
  } else {
    countdown(n - 1);
  }
}

console.time('countdown time');
countdown(100000);
// 出力
// !!!/Users/minami/Documents/programs/js/practice/practice.js:14!!!
// !!!  function countdown(n) {!!!
// !!!                    ^!!!
// !!!RangeError: Maximum call stack size exceeded!!!
// !!!vimshell: exit 8 "node practice.js"!!!

ここまではまあ普通の挙動ですね。

そこで、countdownの再帰呼び出し部分をsetTimeOutでラップしてみる。

function countdown(n) {
  if (n === 0) {
    console.log("done");
    console.timeEnd('countdown time');
  } else {
    setTimeOut(function() {
      countdown(n - 1);
    }, 0);
  }
}
// 出力
// done
// countdown time: 118707ms

スタックオーバローが起きなくなりました！！やったね！！！

何をやってるのかと言うと、setTimeOutを待ち時間0で呼び出す事によって、再帰呼び出し部分をJavaScriptのイベントキューの中に入れてます。JavaScriptのイベントループによって再帰呼び出しが行われる訳です。関数自体は即座にリターンされる為、スタックオーバーフローは起こしません。

ただ、countdown timeの値を見てもらえば分かる通りめちゃくちゃ時間がかかってますね。。。。 setTimeOutの処理に時間がかかってるのでしょうか？これだけ処理が遅いと、あまり使い道は無いかもですね。。。

追記

分かってる人は分かってると思うのですが、これは末尾再帰の形になっていないとダメです。つまり、再帰呼び出しの返り値を使おうとかしちゃうと、即時リターンってのは出来なくなるので、スタックオーバーフローは避けられない訳です。 もっと言うと、forループに置換え可能って事ですね。

ただ、待ち時間でブロックしない非同期のループを書きたい場合には、再帰関数は有用です。例えば、以下のようなコードはforループでは表現出来ないですよね。

function downloadOneAsync(urls, onsuccess, onfailure) {
  var n = urls.length;

  function tryNextURL(i) {
    if (i >= n) {
      onfailure("all downloads failed");
      return;
    }
    downloadAsync(urls[i], onsuccess, function() {
      tryNextURL(i + 1);
    });
  }
  tryNextURL(0);
}

urlsというurlのArrayを渡して、成功するまで順番に非同期でdownloadをするという処理です。成功した時点で次のダウンロードは取りやめ、かつダウンロード処理中にブロックしない為には、こういった再帰で書くのが良い書き方となります。