Pythonの再帰「ローカル」変数を理解する

Question

私は再帰について学習しており、いくつかの楽しい、わかりやすい方法でそれを適用しようとしています。 （はい、この全体のことは、より良いループのネストされた3によって行われます）

def generate_string(current_string, still_to_place): 
    if still_to_place: 
     potential_items = still_to_place.pop(0) 
     for item in potential_items: 
      generate_string(current_string + item, still_to_place) 
      #print("Want to call generate_string({}, {})".format(current_string + item, still_to_place)) 
    else: 
     print(current_string) 
generate_string("", [['a','b','c'],['d','e','f'],['g','h','i']]) 

私は再帰呼び出しをコメントアウトし、印刷のコメントを解除した場合、それは私がそれを呼び出すことになる期待したい正確に何を印刷します。しかし、printのコメントを外すだけで、空のstill_to_place配列が呼び出されることがわかりますが、私は思った "上の"再帰の[d、e、f]、[g、h、i]

私の理解に欠けているものは何ですか？ありがとう！

Answer 1

私はgenerate_stringの各反復中に得たものを出力しました。これが私のものです。おそらくすべてが混乱しています。何も期待通りに動作していないからですが、Pythonが何を考えているかを説明してください。

#1st time 
current_string = "" 
still_to_place = [['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']] 

は、我々は何が起こるかを歩くと、私たちはまず、第1のアレイ['a', 'b', 'c']ポップ、しかし、上記のデータを渡すことによって開始し、我々はこのポップされた配列を反復処理を開始します。我々は

#2nd time 
current_string = "a" 
still_to_place = [['d', 'e', 'f'], ['g', 'h', 'i']] 

）（0）、我々は今だけ（generate_stringに行われる最初の再帰呼び出しにアレー、still_to_place.pop(0)の後半部分を持っている.popと呼ばれるしかしこれはcurrent_stringにあった正確に何であると再帰呼び出しが初めて行われたときはstill_to_placeになります。今度は、関数を最初からやり直します。 pop関数をもう一度呼び出して、2番目の配列['d', 'e', 'f']を削除します。今は3番目と最後の配列だけが残っています。 still_to_placeが空になっているので、我々は、['g', 'h', 'i']を反復したよう

#3rd time 
current_string = "ad" 
still_to_place = [['g', 'h', 'i']] 

。 （私たちは最後の配列をポップしたばかりです）generate_stringを呼び出すと、else節に直接移動し、 "広告"文字列にちょうどポップした配列の値を加えて印刷します。

#4th, 5th and 6th time 
still_to_place = [] 
current_string = "adg" 

still_to_place = [] 
current_string = "adh" 

still_to_place = [] 
current_string = "adi" 

ここで、2回目の最後の再帰呼び出しが途絶えたところで、ここで続行します。これは物事が混乱するところです。 current_string = "a"とstill_to_placeをオフにしたときには、もともとは[['d', 'e', 'f'], ['g', 'h', 'i']]でしたが、それ以降は配列のすべてがポップされました。あなたは配列が数字や文字列とは異なった振る舞いをすることを見ています。配列のすべてのバージョンは同じデータを共有します。データを一度変更すると、配列が使用されているどこでも変更されます。 （オブジェクトと辞書もこのように動作します）。still_to_place = []と言われているので、残りの再帰呼び出しではstill_to_placeは空のままです。 potential_itemsには、まだポップされたデータが['d', 'e', 'f']になります。我々はすでに＃4ステップ、＃5、＃6で「D」の文字列を実行してきたので、私たちは

の

#7th and 8th times 
still_to_place = [] 
current_string = "ae" 

still_to_place = [] 
current_string = "af" 

をしたところ、私たちはもう一度['a', 'b', 'c']を持ってpotential_items終えることができると我々はすでに「実行しました' still_to_placeとは異なり、potential_itemsはスコープの小さいローカル変数です。スコープの仕組みがわかっている場合は、複数のpotential_itemを持つ理由は同じですが、使用されているのと同じstill_to_placeです。私たちはstill_to_placeから項目をポップするたびに、ポップされた結果を新しい潜在的項目変数に追加しました。 still_to_placeはプログラム全体に渡ってグローバルなものだったので、still_to_placeへの変更は予期しないところで変更を引き起こします。

うまくいけば、私は物事をより混乱させ、あまり混乱させないようにしました。より明確な説明が必要な場合はコメントを残してください。

Answer 2

これは正常な動作です。なぜなら、各関数呼び出しの間では、still_to_placeが共有されているからです。 Pythonの可変オブジェクトは '代入によって渡されます'。つまり、関数にリストを渡すと、その関数はSAMEリストへの参照を共有します。 This thread has more detail.

したがって、still_to_place.pop（0）を呼び出すたびに、すべての再帰呼び出しでリストがポップされます。彼らはまったく同じリストを共有しています。

この動作は常に望ましいとは限りません。多くの場合、リストを不変にしたいことがあります。この場合、再帰呼び出しにデータ構造の変更されたコピーを渡す必要があります。ここにあなたのコードは不変のアプローチを使用して次のようになります：インプレース、それを変更します親指のルール、オブジェクトのメソッド（例えば.pop）として

def generate_string(current_string, still_to_place): 
    if still_to_place: 
     potential_items = still_to_place[0] 
     for item in potential_items: 
      generate_string(current_string + item, still_to_place[1:]) 
      print("Want to call generate_string({}, {})".format(current_string + item, still_to_place)) 
    else: 
     print(current_string) 
generate_string("", [['a','b','c'],['d','e','f'],['g','h','i']]) 

。また、異なる言語が異なる方法でアプローチします。言語によっては、データ構造が常に不変です。