こんにちは
再帰法を使ったアルゴリズムを考えているのですが、同じ流れを持つ関数でも引数の違いによってstack level too deep
が出たり出なかったりします
例えば、「男女を30人、女子が隣合わないように並べる」方法の数を求める関数の場合
ruby
1#引数に文字列を使う場合 2N = 30 3def pattern1(seq) 4 return 1 if seq.length == N 5 6 sum = pattern1(seq + "b") 7 sum += pattern1(seq + "g") if seq[-1] == "b" 8 return sum 9end 10 11p pattern1("b") + pattern1("g") 12#2178309
ruby
1N = 30 2#引数に配列を使う場合 3def pattern2(array) 4 return 1 if array.length == N 5 6 sum = pattern2(array << "b") 7 sum += pattern2(array << "g") if array[-1] == "b" 8 return sum 9end 10 11p pattern2(["b"]) + pattern2(["g"]) 12#`pattern2': stack level too deep (SystemStackError)
となります
こちらのサイトなどを見て、呼び出し元メソッドが確保している変数などの領域によって再帰の限界が変わるとかは書いてあるのですが、つまりはどういうことなのでしょうか?
とどのつまりは
- なぜ今回は前者がうまくいって後者がうまくいかないのか
- 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)
こちらの場合は、いわゆるスタックに情報をためすぎた、つまり変数が多すぎたから起きたものになるのでしょうか?
よろしくお願いいたします
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2016/06/28 05:57
2016/06/28 07:04