JavaScriptの再帰の回数制限を超える実験をしてみる

JavaScriptで再帰をすると、ブラウザによって再帰できる回数が違います。

ブラウザごとに何回再帰できるかを検証する記事がいくつかありました。

Firefoxだと3,000回あたりが再帰回数の限界のようですね。

実験の概要

ということで、単純な等差数列の和を求めるコードを実行して、再帰回数の限界について実験してみました。*1

実験1

Firefoxで3,000回実行できるかどうか確認してみます。

var arithmetic_progression = function(n) {
  var a = 0;
  return (function(n) {
    if (n < 1) return console.log(a);
    a += n;
    n--;
    arguments.callee(n);
  })(n);
};

arithmetic_progression(3000);

// 結果:
// InternalError: too much recursion

エラーがでますね。同じコードをSafariで実行するとちゃんと値が出ました。

実験2

Firefoxでは3,000回再帰を実行することは不可能ということがわかりましたが、これをsetTimeoutを使った方法に置き換えると、回数制限を超えることができます。setTimeoutで擬似マルチスレッドを実現できるとか言うので、イメージ的にはなんとなくできそうな感覚があっても、なぜうまくいくのかという理屈はわかってません。再帰はスタックを使って、setTimeoutはキューを使うからってことだろうか。

var arithmetic_progression = function(n) {
  var a = 0;
  return (function(n) {
    if (n < 1) return console.log(a);
    a += n;
    n--;
    setTimeout(arguments.callee, 0, n);
  })(n);
};

arithmetic_progression(3000);

// 結果:
// 4501500

これで、再帰の制限数3,000を超えることができました。しかし、恐ろしく値が出るのが遅い。setTimeoutの待ち時間が0なのに、なぜこんなに時間がかかるのかの理屈もわかりません。実験1のコードで、引数に2,900を渡した時とか、すぐに値が出るのに。

とりあえず、再帰の回数制限は、この方法で超えられるようです。時間はかかりますが、30,000とか渡しても値が出ました。実用性はなさそうですが。。。

実験3

遅すぎても仕方ないので、try〜catchを使って、制限ギリギリまで再帰して、制限が超えた時にsetTimeoutに置き換えたらどうなるかを試してみます。

var arithmetic_progression = function(n) {
  var a = 0;
  return (function(n) {
    if (n < 1) return console.log(a);
    a += n;
    n--;
    try {
      arguments.callee(n);
    }
    catch(e) {
      setTimeout(arguments.callee, 0, n);
    }
  })(n);
};

arithmetic_progression(3000);

// 結果:
// 4501500

これで実行したら、割と早く値が出ました。

SafariとかChromeに関して言うと、3,000,000くらいを引数に与えても、それなりの早さで値を出してくるので、すげー！と感心しました。

実験4

try〜catchの部分がどのように処理されているかを確認してみます。

注意: 以下、Safari、Chromeではハングアップします。

var arithmetic_progression = function(n) {
  var a = 0;
  return (function(n) {
    if (n < 1) return console.log(a);
    a += n;
    n--;
    try {
      console.log('try! 引数n: ' + n + ' 戻り値a: ' + a);
      arguments.callee(n);
    }
    catch(e) {
      console.log('catch! 引数n: ' + n + ' 戻り値a: ' + a);
      setTimeout(arguments.callee, 0, n);
    }
  })(n);
};

arithmetic_progression(3000);

// 結果:
// try! 引数n: 2999 戻り値a: 3000
// 以下省略
// 4501504

ログを見ると、catchで例外を受けた後は、tryに戻ってるみたいなので、一回setTimeoutで処理したら、次の再帰回数の制限まで再帰してるっぽい。

でも、ログを吐く処理を挟むと結果の値がずれてる。具体的にはcatchで例外を受けた部分が重複加算されてしまってる。

なんで、ログを吐く処理を挟まないと正しい値が出るのかが謎。

となると、実験3は、たまたまうまくいっただけの超不安定なコードだったりするのかも。

結論

理屈がわかりません。*2 *3

*1:Firebug、またはSafari(Chrome)の開発ツール使用前提

*2:わからないだらけで微妙なエントリーになってしまい、申し訳ない限りです

*3:ここまでIEなし

あと味

たくさん情報を食べて、たくさん発信すると、あとになって味わい深い。

JavaScriptの再帰の回数制限を超える実験をしてみる

実験の概要

実験1

実験2

実験3

実験4

結論