質問編集履歴

1 文章追加

dialbird

dialbird score 347

2016/06/28 14:53  投稿

rubyの再帰の限界を知りたい
こんにちは
再帰法を使ったアルゴリズムを考えているのですが、同じ流れを持つ関数でも引数の違いによって`stack level too deep`が出たり出なかったりします
例えば、「男女を30人、女子が隣合わないように並べる」方法の数を求める関数の場合
```ruby
#引数に文字列を使う場合
N = 30
def pattern1(seq)
   return 1 if seq.length == N
   sum = pattern1(seq + "b")
   sum += pattern1(seq + "g") if seq[-1] == "b"
   return sum
end
p pattern1("b") + pattern1("g")
#2178309
```
```ruby
N = 30
#引数に配列を使う場合
def pattern2(array)
   return 1 if array.length == N
   sum = pattern2(array << "b")
   sum += pattern2(array << "g") if array[-1] == "b"
   return sum
end
p pattern2(["b"]) + pattern2(["g"])
#`pattern2': stack level too deep (SystemStackError)
```
となります
[こちらの](http://mizti.hatenablog.com/entry/20121113)サイトなどを見て、呼び出し元メソッドが確保している変数などの領域によって再帰の限界が変わるとかは書いてあるのですが、つまりはどういうことなのでしょうか?
とどのつまりは
1. なぜ今回は前者がうまくいって後者がうまくいかないのか
2. rubyで再帰を使う場合に、このような事態を避けるための方法
が知りたいです
よろしくお願いいたします。
よろしくお願いいたします。
以下追加文
おかげさまで、今回の件が参照型の扱いによるものであるとわかりました。
ですが、実はもう一つスタックオーバーフローしてしまう例があるのでこちらも質問させてください
こちらも上と同様の問題を解くために作った関数なのですが、(gが女子の残り人数、bが男子の残り人数、boolがtrueならば次に女子を並べてもいいという意味)こちらもアウトらしいです
```
def pattern3(g, b, bool)
   return 0 if g > 1 && b == 0
   return 1 if g == 0
   sum = 0
   if bool
       sum += pattern3(g-1, b, false)
       sum += pattern3(g, b-1, true)
   else
       sum += pattern3(g, b-1, true)
   end
   return sum
end
#適当に値を入れて実行
p pattern3(14,16,true)
#stack level too deep (SystemStackError)
```
こちらの場合は、いわゆるスタックに情報をためすぎた、つまり変数が多すぎたから起きたものになるのでしょうか?
よろしくお願いいたします
  • Ruby

    17362 questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

思考するエンジニアのためのQ&Aサイト「teratail」について詳しく知る