Verstehen "lokale" Variable Rekursion in Python

Question

Ich lerne gerade über Rekursion und versuche, es in etwas für Spaß anzuwenden, kommen-zu-verstehen-Wege. (Ja, das Ganze ist besser durch drei for-Schleifen verschachtelt getan)

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']]) 

Wenn ich den rekursiven Aufruf Kommentar und Kommentar- der Druck, druckt es genau das, was ich hoffe, würde es nennen würde. Das Auskommentieren des Ausdrucks zeigt jedoch, dass es ein leeres still_to_place-Array aufruft, selbst wenn es noch die [d, e, f], [g, h, i] von der "höheren" Rekursion haben sollte, denke ich.

Was vermisse ich in meinem Verständnis? Vielen Dank!

Answer 1

Ich habe ausgegeben, was ich bei jeder Iteration von generate_string bekommen habe und das habe ich bekommen. Es ist wahrscheinlich alles verwirrend, weil sich nichts so verhält, wie du es erwartet hast, aber lass mich erklären, was Python denkt.

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

Wir beginnen, indem sie in den obigen Daten vorbei, aber, wie wir durch gehen, was passiert, wir zuerst das erste Array Pop ['a', 'b', 'c'], und wir beginnen, durch diese knallte Array zu durchlaufen. Doch weil wir .pop (0) genannt, wir jetzt nur noch den letzten Teil des Arrays haben, die still_to_place.pop(0) auf dem ersten rekursiven Aufruf, die generate_string gemacht wird()

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

Das ist genau das, was in current_string und still_to_place beim ersten Aufruf des rekursiven Aufrufs. Jetzt fangen wir an, die Funktion von Anfang an erneut auszuführen. Wir rufen die Pop-Funktion erneut auf und entfernen das zweite Array ['d', 'e', 'f']. Jetzt ist nur noch das dritte und letzte Array übrig.

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

Als wir durch ['g', 'h', 'i'] laufen, weil still_to_place jetzt leer ist. (Wir haben gerade das letzte Array aufgerufen.) Alle Aufrufe von generate_string gehen direkt zur else-Klausel, und wir werden die "ad" -String plus die Werte in dem Array ausgeben, das wir gerade gepoppt haben.

Wir fahren jetzt fort, wo der letzte rekursive Aufruf aufhörte, als wir das zweite Mal durchgingen. Hier werden die Dinge verwirrend. Als wir aufgehört haben current_string = "a" und still_to_place war ursprünglich [['d', 'e', 'f'], ['g', 'h', 'i']], aber wir haben seitdem alles aus dem Array popped. Sie sehen, Arrays verhalten sich anders als Zahlen oder Strings. Alle Versionen eines Arrays teilen die gleichen Daten. Sie ändern die Daten einmal, sie ändern sie überall dort, wo das Array verwendet wird. (Objekte und Wörterbücher verhalten sich auch auf diese Weise.)

Also mit allem, was still_to_place = [] und still_to_place gesagt wird bleiben leer für den Rest der rekursiven Aufrufe. potential_items hat immer noch die Daten, die es von ['d', 'e', 'f'] abgerufen hat. Wir haben bereits ausgeführt, um die ‚d‘ string in den Schritten # 4, # 5 und # 6, so können wir beenden, wo wir von

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

still_to_place = [] 
current_string = "af" 

wieder einmal links potential_items hat ['a', 'b', 'c'] und wir haben bereits ausgeführt ‚ein ". Im Gegensatz zu still_to_place ist potential_items eine lokale Variable mit einem kleineren Bereich. Wenn Sie wissen, wie Bereiche arbeiten, dann wird es machen, warum wir mehrere potential_items haben können, aber es ist derselbe still_to_place, der verwendet wurde. Jedes Mal, wenn wir ein Element von still_to_place löschten, fügten wir das Ergebnis popping einer neuen potenziellen Elementvariablen mit einem begrenzten Bereich hinzu. still_to_place war global für das gesamte Programm, und so führte eine Änderung an still_to_place zu Änderungen, die nicht erwartet wurden.

Hoffentlich machte ich die Dinge verwirrender und nicht weniger verwirrend. Hinterlasse einen Kommentar, zu dem du mehr Klarheit brauchst.

Answer 2

Richtig, das ist das erwartete Verhalten. Der Grund ist, dass still_to_place zwischen jedem Funktionsaufruf geteilt wird. Veränderbare Objekte in Python werden an Zuweisung übergeben, was bedeutet, dass wenn Sie eine Liste an eine Funktion übergeben, diese Funktion einen Verweis auf die SAME-Liste hat. This thread has more detail.

Also, jedes Mal, wenn Sie still_to_place.pop (0) aufrufen, rufen Sie die Liste bei jedem rekursiven Aufruf auf. Sie alle teilen die exakt gleiche Liste.

Dieses Verhalten ist nicht immer wünschenswert, oft möchten Sie, dass Ihre Liste unveränderbar ist. In diesem Fall müssen Sie Ihrem rekursiven Aufruf eine geänderte Kopie der Datenstruktur übergeben. Hier ist, was Ihr Code wie mit dem unveränderlichen Ansatz aussehen:

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']]) 

Als Faustregel gilt: Methoden für das Objekt (z .pop) wird es an Ort und Stelle ändern. Auch verschiedene Sprachen nähern sich Mutabilität unterschiedlich an, in einigen Sprachen sind Datenstrukturen IMMER unveränderlich.