2009-07-16

Javascriptはどのくらい再帰できるのか

実際に試してみた。まず、現状で末尾再帰を最適化するJavascriptの実装はない。では具体的に何回ぐらい再帰できるのかという話だが、すべてのブラウザで、まず十分だろうというぐらいはできるようだ。再帰関数の内容によっても、上下するのかも知れないが、まあ、再帰でループを書くような極端なことをしない限りは、実用上問題ないだろう。

結局、末尾再帰の最適化をしても、ほとんどのWebサイトでは恩恵を得られない事実があるのだろう。C++だって、有名どころのコンパイラは末尾再帰を最適化しているのだが、そもそもC++で末尾再帰の最適化が必要なコードを書くプログラマーは、かなり少数だと思われる。

尚、IEはDOMのサポートはおろか、application/javascriptすら無視するというやる気のないブラウザなので、このテストは実行できない。IE8で実行できるような同等のコードを書いて実行してみたが、2455回の再帰ができた。Firefoxもそれぐらいの再帰ができるので、現行のJavascriptプログラマは、二千回は再帰できるということを目安にするべきだと思う。二千回というのは、通常のHTMLのDOMを再帰的に巡回するとか、Javascriptで現実的に扱うぐらいの要素数の配列のクイックソートを実装するとか、それぐらいのことなら十分できるはずだ。IE6は知らん。

2 comments:

  1. Rhino はオプションによっては末尾再帰の最適化をするようです。

    ReplyDelete
  2. iPhone3GSで40326と出ました

    ReplyDelete

You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.