JavaScriptの再帰の回数制限を超える実験をしてみる
JavaScriptで再帰をすると、ブラウザによって再帰できる回数が違います。
ブラウザごとに何回再帰できるかを検証する記事がいくつかありました。
- 各ブラウザのJSランタイムがどこまで再帰できるか試してみた、という。 - muddy brown thang
- javascriptの再帰処理の限界 - 電脳戦士ハラキリ -SE道とは死ぬ事と見つけたり-
- JS の再帰 (追試) - 冬通りに消え行く制服ガールは✖夢物語にリアルを求めない。 - subtech
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は、たまたまうまくいっただけの超不安定なコードだったりするのかも。