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

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

ただいまの
回答率

87.93%

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

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,882

score 347

こんにちは
再帰法を使ったアルゴリズムを考えているのですが、同じ流れを持つ関数でも引数の違いによってstack level too deepが出たり出なかったりします

例えば、「男女を30人、女子が隣合わないように並べる」方法の数を求める関数の場合

#引数に文字列を使う場合
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
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)


となります

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

とどのつまりは

  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)


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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+1

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/06/28 14:54

    maisumakunさん
    迅速なるご返答ありがとうございます。
    おっしゃる通り、arrayをarray.cloneにしてコピーしたらできました!ありがとうございます!

    もしよろしければもう一つ質問を追加したのでよろしくお願いいたします........

    キャンセル

  • 2016/06/28 15:15

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

    キャンセル

  • 2016/06/28 16:02

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

    本当にありがとうございました!

    キャンセル

+1

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

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

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

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

追記分

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/06/28 14:57

    Zuishinさん
    迅速かつ詳細なご返答、ありがとうございます

    メモリにも種類があるのですね。勉強になります。

    そしてもしよろしければ、もう一つわからないことがあるので、お時間がございましたら是非ともよろしくお願いいたします........。

    キャンセル

  • 2016/06/28 16:04

    おっしゃる通りですね........
    自分の浅学さが身にしみました

    これからはより注意させていただきます。
    丁寧な回答、誠にありがとうございました!

    キャンセル

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

  • ただいまの回答率 87.93%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る