質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Ruby

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

Q&A

解決済

2回答

2658閲覧

rubyの再帰の限界を知りたい

dialbird

総合スコア379

Ruby

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

2グッド

1クリップ

投稿2016/06/28 05:29

編集2016/06/28 05:53

こんにちは
再帰法を使ったアルゴリズムを考えているのですが、同じ流れを持つ関数でも引数の違いによって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)

となります

こちらのサイトなどを見て、呼び出し元メソッドが確保している変数などの領域によって再帰の限界が変わるとかは書いてあるのですが、つまりはどういうことなのでしょうか?

とどのつまりは

  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)

こちらの場合は、いわゆるスタックに情報をためすぎた、つまり変数が多すぎたから起きたものになるのでしょうか?
よろしくお願いいたします

ozwk, DrqYuto👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ローカル変数は通常スタックと呼ばれる領域に格納されます。
グローバル変数は通常ヒープと呼ばれる領域に格納されます。
これらは原則であって絶対ではありません。コンパイラの判断で変わることもあります。
いずれにせよ、プログラムで使えるメモリには二種類あります。

それを踏まえて、再帰を呼び出すと、呼び出された関数で再度ローカル変数の領域がスタックに再確保されます。そして、これ以上確保できなくなった時、スタックオーバーフローというエラーになります。

つまり、スタックオーバーフローになるかならないかは、
1. スタックがどの程度の大きさを持っているか(コンパイラオプションなどで指定できることもあります)
2. ローカル変数にどの程度のメモリが必要なのか(変数の型、宣言する数、コンパイラによる最適化などによって変わります)
3. 再帰の回数
の二つで主に決まります。

通常の関数呼び出しの場合、関数が終了した時点でスタックに積まれたローカル変数の領域は解放されますが、再帰の場合、呼び出し側の変数は呼び出された側が終了するまで解放されません。
このため、スタックオーバーフローが起きやすくなります。

###追記分

Ruby

1return 0 if g > 1 && b == 0 2return 1 if g == 0

この部分が問題ですね。
g == 1 && b == 0
の時、次の条件に移りますが、ここで bool が true だと、b < 0 となって永遠に再帰が終わりません。

スタックオーバーフローが出るときには、変数が多すぎるとかなんとかいうより以前に、ほぼ無限ループが原因です。
無限にループしていないかどうか、関数内で変数の内容やループ回数をダンプしながらデバッグされたらいいと思います。

投稿2016/06/28 05:46

編集2016/06/28 06:26
Zuishin

総合スコア28656

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

dialbird

2016/06/28 05:57

Zuishinさん 迅速かつ詳細なご返答、ありがとうございます メモリにも種類があるのですね。勉強になります。 そしてもしよろしければ、もう一つわからないことがあるので、お時間がございましたら是非ともよろしくお願いいたします........。
dialbird

2016/06/28 07:04

おっしゃる通りですね........ 自分の浅学さが身にしみました これからはより注意させていただきます。 丁寧な回答、誠にありがとうございました!
guest

0

ベストアンサー

2のほうが上手く動かないのは、プログラム側のバグです。

Rubyで引数は参照の値渡しになりますので、再帰の際に渡したarrayは、親の関数と同じオブジェクトです。そして、array << hogeはこの配列へ値を破壊的に追加しますので、if array[-1] == "b"が成立した際には、一気に2個追加されてしまうことがあります。

2個追加されたことで、array.length > Nとなってしまえば、もはや再帰を止める条件は何も存在しません。スタックを食い尽くすまで実行されてしまいます。

投稿2016/06/28 05:38

maisumakun

総合スコア145121

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

dialbird

2016/06/28 05:54

maisumakunさん 迅速なるご返答ありがとうございます。 おっしゃる通り、arrayをarray.cloneにしてコピーしたらできました!ありがとうございます! もしよろしければもう一つ質問を追加したのでよろしくお願いいたします........
maisumakun

2016/06/28 06:15

「その3」の場合も、g=1かつb=0の状態から無限にbが減っていくパターンが、再帰を止める条件から抜けています。
dialbird

2016/06/28 07:02

ありがとうございます! スタックどうこう以前に、もっと自分の詰めの甘さを見直そうと思います........。 本当にありがとうございました!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問