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

Question

ただいま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の出番がないのでは、とも
思うようになってしまいました。頭から湯気が出ています。
もし助けて頂ける方がいらっしゃいましたら、どうぞ、よろしくお願い致します。

Answer 1

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

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 []

Comments

[tuvalu]

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

Answer 2

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

Comments

[tuvalu]

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

[tuvalu]

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

[defghi1977]

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

Answer 3

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]

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

Comments

[tuvalu]

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

[tuvalu]

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

[tuvalu]

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

[tuvalu]

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

[tuvalu]

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

[defghi1977]

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

[tuvalu]

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