Rubyの再帰の限界を調べてみる
深さ優先探索の問題（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160）を
解いていたら手元のサンプルインプットではうまく動くのだけど、
Online Judgeに投げ込むとうまく動かない。（Runtime Errorとのこと）
ためしに問題の上限サイズで入力例を作ったら、
a.rb:11: stack level too deep (SystemStackError)
みたいなエラーがでたので再帰が深すぎてエラーに成ってるのではないか。
def func(n)
if n == 1 then
return "hoge"
elsif n > 1
#p n
func(n-1)
end
end
p func ARGV[0].to_i
っていうスクリプトを作っていろいろ引数を変えて動かしてみる。
ruby --version
ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-linux]
# ruby stacktest.rb 8735
だと
stacktest.rb:2: stack level too deep (SystemStackError)
# ruby stacktest.rb 8734
だと
"hoge"
と表示されるので、このコード・環境での再帰の限界は8734回までということになる。
ruby --version
ruby 1.8.7 (2012-06-29 patchlevel 370) [x86_64-linux]
に切り替えると、
# ruby stacktest.rb 5727
"hoge"
# ruby stacktest.rb 5728
stacktest.rb:6:in `func': stack level too deep (SystemStackError)
from stacktest.rb:6:in `func'
from stacktest.rb:9
になるので、5727回まで。
また1.9.3に戻して、
def func(n)
if n == 1 then
return "hoge"
elsif n > 1
arr = Array.new [" "]
return func(n-1)
end
end
p func ARGV[0].to_i
っていう形で関数が余計なarrを保持するようにすると、8188回までで打ち止め。
arrを削ったら8734回まで行けるようになった。
というわけで、
- 呼び出し元メソッドが確保している変数などの領域を増やすと
スタック呼び出し可能な深さが減る
- RubyのVersionによってもスタック呼び出し可能な深さが減る
ということは分かった...けど直接的に呼び出し可能回数をもっと増やすにはどうしたらいいかは
よくわからないままです（オチなし）
-
-
-
- -
-
-
追記: コメントでRuby2.0以降では、環境変数にRUBY_THREAD_VM_STACK_SIZEを設定することでスタックサイズが設定できると情報をいただきました。
