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

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

ただいまの
回答率

90.76%

  • Ruby

    7032questions

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

再帰のコードで何が起きているのかわからなくなってしまいます。

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 161

tuvalu

score 103

ただいまRubyで再帰を理解しようとしています。(後で追加:順列の列挙(検索用))
でも、途中でで何が起きているのかわからなくなってしまいます。
コード自体が切り貼りで間違っているかもしれません。。おかしな勘違いをしているかもしれません。
よろしければ教えてください。よろしくお願い致します。

def permutation(ary, new_ary = [])
  p new_ary if ary.length == new_ary.length

  ary.each do |n|
    next if new_ary.member? n
    new_ary.push n
    permutation(ary, new_ary)
    new_ary.pop
  end
end

permutation([1,2,3])
結果
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]


うまく動いているようです。が、どう動いてこうなるのかを知りたく、
next if p new_ary.member? n と見えるようにして、あと
p new_ary.push n
p new_ary.pop と見えるようにしました。

結果(長くてすみません)
false
[1]
true
false
[1, 2]
true
true
false
[1, 2, 3]
[1, 2, 3]
true
true
true
3
2
false
[1, 3]
true
false
[1, 3, 2]
[1, 3, 2]
true
true
true
2
true
3
1
false
[2]
false
[2, 1]
true
true
false
[2, 1, 3]
[2, 1, 3]
true
true
true
3
1
true
false
[2, 3]
false
[2, 3, 1]
[2, 3, 1]
true
true
true
1
true
true
3
2
false
[3]
false
[3, 1]
true
false
[3, 1, 2]
[3, 1, 2]
true
true
true
2
true
1
false
[3, 2]
false
[3, 2, 1]
[3, 2, 1]
true
true
true
1
true
true
2
true
3


これを見ると、最初に引数aryの配列の1番目が、変数new_aryにあるか見て、無いのでnew_aryに代入しています。
次に再帰でメソッドpermutation([1,2,3], [1])を呼んでいるものと理解しています。

2回目のeachで、今度は引数aryの配列の1番目が、変数new_aryにあるので、次のnを評価して、これまたないので、new_aryに2を代入。
次に再帰でメソッドpermutation([1,2,3], [1,2])を呼んでいるものと理解しています。

3回目のeachで、今度は引数aryの配列の1番目も2番目も変数new_aryにあるので、次のnを評価して、new_aryに3を代入。
次に再帰でメソッドpermutation([1,2,3], [1,2,3])を呼んでいるものと理解しています。

そのあとから急にわからなくなってしまいます。表示されている結果は
true
true
true
ここまではまだそうだなあと思えるのですが、次に
3
2
false
[1,3]
となり、もうわからなくなってしまいました。
しまいにはpermutationに再帰するのなら、new_ary.popの出番がないのでは、とも
思うようになってしまいました。頭から湯気が出ています。
もし助けて頂ける方がいらっしゃいましたら、どうぞ、よろしくお願い致します。

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 3

+3

理解を助けるためにちょいとソース弄って無駄を排除およびデバッグ出力を追加してみました

def permutation(ary, new_ary = [], level = 0)
  return puts "  " *level + "OUT=> #{new_ary.inspect}" if ary.length == new_ary.length
  puts "  " *level + "Enter #{new_ary.inspect}"

  (ary - new_ary).each do |n|
    new_ary.push n
    permutation(ary, new_ary, level + 1)
    new_ary.pop
  end
  puts "  "*level + "Leave #{new_ary.inspect}"
end

permutation([1,2,3])

結果は

Enter []
  Enter [1]
    Enter [1, 2]
      OUT=> [1, 2, 3]
    Leave [1, 2]
    Enter [1, 3]
      OUT=> [1, 3, 2]
    Leave [1, 3]
  Leave [1]
  Enter [2]
    Enter [2, 1]
      OUT=> [2, 1, 3]
    Leave [2, 1]
    Enter [2, 3]
      OUT=> [2, 3, 1]
    Leave [2, 3]
  Leave [2]
  Enter [3]
    Enter [3, 1]
      OUT=> [3, 1, 2]
    Leave [3, 1]
    Enter [3, 2]
      OUT=> [3, 2, 1]
    Leave [3, 2]
  Leave [3]
Leave []

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/04/13 16:55

    たいへんありがとうございます。助かります。

    キャンセル

checkベストアンサー

+2

rubyは知りませんが, 大体の内容は把握できました.

def permutation(ary, new_ary = [])
  p new_ary if ary.length == new_ary.length

  ary.each do |n|  #(a)
    next if new_ary.member? n
    new_ary.push n
    permutation(ary, new_ary)
    new_ary.pop
  end
end


(a)のループはかいつまんで言うと, 配列arrの中でまだ選ばれていない(new_arrに存在しない)の値のみで繰り返されるループです.
NOTE:new_ary.popは呼び出し元に影響を及ぼさないようにするための後処理です.

従って全体の処理の流れとしてはまず大本の(a)ループが発生するため,

  • 最初に1を選んだケース
  • 最初に2を選んだケース
  • 最初に3を選んだケース

となります.

で, (a)のループは再帰処理により(a)のループを呼び出しますが, その際既に選ばれているものについてはループが除外されるため…

  • 最初に1を選んだケース
    + 二番目に2を選んだケース
    + 二番目に3を選んだケース
  • 最初に2を選んだケース
    + 二番目に1を選んだケース
    + 二番目に3を選んだケース
  • 最初に3を選んだケース
    + 二番目に1を選んだケース
    + 二番目に2を選んだケース

の順に処理が行われることになります. また, (a)のループは再帰処理により(a)のループを呼び出すため,

  • 最初に1を選んだケース
    + 二番目に2を選んだケース
    ーー 三番目に3を選んだケース
    + 二番目に3を選んだケース
    ーー 三番目に2を選んだケース
  • 最初に2を選んだケース
    + 二番目に1を選んだケース
    ーー 三番目に3を選んだケース
    + 二番目に3を選んだケース
    ーー 三番目に1を選んだケース
  • 最初に3を選んだケース
    + 二番目に1を選んだケース
    ーー 三番目に2を選んだケース
    + 二番目に2を選んだケース
    ーー 三番目に1を選んだケース

の順に処理が行われることになります.

さて, この三段目のループで再帰処理が呼び出されると, 関数の一行目の条件に合致することからnew_aryの内容・つまりarrの中の要素の選んだ順が出力されることになるので...

  • 最初に1を選んだケース
    + 二番目に2を選んだケース
    ーー 三番目に3を選んだケース>>>[1,2,3]
    + 二番目に3を選んだケース
    ーー 三番目に2を選んだケース>>>[1,3,2]
  • 最初に2を選んだケース
    + 二番目に1を選んだケース
    ーー 三番目に3を選んだケース>>>[2,1,3]
    + 二番目に3を選んだケース
    ーー 三番目に1を選んだケース>>>[2,3,1]
  • 最初に3を選んだケース
    + 二番目に1を選んだケース
    ーー 三番目に2を選んだケース>>>[3,1,2]
    + 二番目に2を選んだケース
    ーー 三番目に1を選んだケース>>>[3,2,1]

の順番に配列の内容が出力されたのです.

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/04/13 07:58

    先日と同様、早々のご回答ありがとうございます!
    前回よりも難しいと思っています。
    ゆっくりと咀嚼し、しっかり消化させていただきます。m__m

    キャンセル

  • 2018/04/13 11:40

    大変恐縮ですがよろしいでしょうか?
    defghi1977さんに教えて頂いた内容と、出力結果と、あと先ほどte2jiさんに教えて頂いたサイトで一手づつ三つ巴で順を追っていますが、そのページ(https://goo.gl/R67dSo)の実行展開のなかで
    45手めで一巡してループ処理が正常に終了するのに、46手めで急にループの中の半ばにある
    再帰を呼び出す(呼び出せる)ところが、たぶんここが急にわからなくなってしまうポイントかと思われます。
    ここがわかれば次に進めると思います。ご教授ください。よろしくお願い致します。失礼いたします。

    キャンセル

  • 2018/04/13 11:46 編集

    ループが終わってから改めて呼んでいるのではなく、再帰処理が終わったから
    その続きでそこから次の行に移った、という訳ですね。
    わかってきた気がしてきました。
    度々のご回答ありがとうございます。

    キャンセル

  • 2018/04/13 11:58

    これで質問のなかにあった、
    しまいにはpermutationに再帰するのなら、new_ary.popの出番がないのでは、とも思うようになってしまいました。
    というところもクリアできそうです!

    キャンセル

  • 2018/04/13 12:37

    ループのなかにある再帰文より上に記述されている処理が再帰処理中のループ処理、
    そして再帰文より下に記述されている処理が再帰処理が終わったあとのループ処理、
    ということで、よろしかったでしょうか?

    キャンセル

  • 2018/04/13 12:46

    なんか言ってる意味が判らんけれど. ループに拘ると見えてるものも見えなくなると思うよ.
    再帰処理は「似た構造の繰り返し」に用いるテクニックで, 今回は{1, 2, 3}というデータに対し, その各ノードに{1, 2, 3}がぶら下がっていて, 更にその下にも{1, 2, 3}がぶら下がっているデータ構造を(ループと再帰で)順に辿っているというのがミソなんだ.
    コレに似た構造としてはディレクトリ構造やDOMツリー等が考えられるでしょう.

    キャンセル

  • 2018/04/13 13:42

    なんかわかった気になって喜んでいたのですが、どうも勘違いのようです。
    いろいろ教えていただきありがとうございました。
    少し休憩します。。

    キャンセル

+2

Python Tutor
こちらで挙動を追うとわかりやすいと思います。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/04/13 08:21

    ありがとうございます。
    見たことない画面で、まだ使い方がわかりませんがおもしろそうです!
    今後も使えますか?
    ごめんなさい。ベストアンサーは昨夜ご指導頂いた方にしています。
    今後ともよろしくお願い致します。失礼します。

    キャンセル

  • 2018/04/13 11:30

    大変恐縮ですがよろしいでしょうか?
    教えて頂いたサイトで一手づつ順を追って理解していますが、
    45手めで一巡してループ処理が正常に終了するのに、46手めで急にループの中の半ばにある
    再帰を呼び出す(呼び出せる)のですか?
    たぶんここが急にわからなくなってしまうポイントかと思われました。
    ここがわかれば次に進めると思います。ご教授ください。よろしくお願い致します。

    キャンセル

  • 2018/04/13 11:33

    再帰処理として呼び出した
    permutation(ary, new_ary)
    が完了したので, 次の行に処理が移っただけだよ

    キャンセル

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

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

関連した質問

  • 解決済

    Rubyのリファクタリング方法について

    こんにちは。 Ruby2,Rails4の環境でアプリケーションを開発しています。 リファクタリングについて質問させてください。 以下のようなコードがあり、配列で渡された値

  • 解決済

    ハッシュにして出力したい

    下記humans.csvをrbファイルで読み取って、記載した実行結果を出したいです。その際、途中まで書いて下記記載しているrbファイルのコードを使って出したいのですがどのように続き

  • 解決済

    Ruby eachとif文が入れ子になった処理を終える

     超初歩的な質問で申し訳無いのですが、以下の様な処理があった時に、cだったらif文とeach文を抜けて、trueを出力するためにはどのような処理を加えればよいですか? 現状ですと

  • 解決済

    2個ずつ追加

    rubyを使って2こずつ追加して比較したいと考えています。 現在のコードだと [[[1, 2], [3, 4]], [[3, 4], [5, 6]], [[5, 6], [7,

  • 解決済

    Ruby 1~100までの数字を素数で出す場合について

    表題の件について、下記のようにコードを組んだのですが、実行結果が空白になるのです。。。   (2..n-1).each do |x|     if  n % x == 0  

  • 解決済

    挿入ソートのプログラムがわかりません。

    1 insertionSort(A, N) // N個の要素を含む0-オリジンの配列A 2   for i が 1 から N-1 まで 3     v = A[i] 4   

  • 解決済

    暇つぶしにどうぞ

    概要 $hrtというサイズ11の配列があります。 それぞれの項目には数値が入り $hrt[0] と $hrt[10] は0固定です。 やりたい事は 項目が0と0で囲ま

  • 解決済

    Rubyでずんどこキヨシ

    お疲れ様です。Takkoです。 現在Rubyを独学しているものです。 一年ほど前SE業界に入り込み、 その際の研修でjavaを使用してずんどこキヨシを作らされたことを思い

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

  • Ruby

    7032questions

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