Wie rekursive Funktionen arbeiten innerhalb einer 'for-Schleife'

Question

Ich bin ziemlich neu in 'rekursive Funktionen'. Ich versuche also, den Grund dafür zu nennen, warum wir rekursive Funktionen verwenden und wie rekursive Funktionen funktionieren, und ich denke, dass ich ein ziemlich gutes Verständnis davon habe.

Vor zwei Tagen habe ich versucht, das Problem des kürzesten Weges zu lösen. Ich habe eine folgende Grafik (es ist in Python):

graph = {'a': ['b', 'c'], 
      'b': ['c', 'd'], 
      'c': ['d'], 
      'd': ['c'], 
      'e': ['f'], 
      'f': ['c']} 

Ich bin nur einen Weg zu finden versuchen, nicht den kürzesten path.So, hier ist der Code:

def find_path(graph,start,end,path=[]): 
    path = path + [start] 
    #Just a Test 
    print(path) 

    if start == end: 
     return path 

    if start not in graph: 
     return None 

    for node in graph[start]: 
     if node not in path: 
      new_path = find_path(graph,node,end,path) 
     if new_path: 
      #Just a test 
      print(path) 
      return new_path 

print(find_path({'a':['b','c'],'b':['c','d'],'c':['d'],'d':['c'],'e': 
['f'],'f':['c']},'a','d')) 

Mein Ausgang Vertex ist 'a' und der Endknoten ist 'd'.

In der vierten Zeile habe ich nur den 'Pfad' gedruckt, um zu sehen, wo der Pfad hinführt.

In Zeile 17 habe ich auch den 'Pfad' gedruckt, wiederum nur zum Testen. Und hier ist das Ergebnis:

['a'] 
['a', 'b'] 
['a', 'b', 'c'] 
['a', 'b', 'c', 'd'] 
['a', 'b', 'c'] 
['a', 'b'] 
['a'] 
['a', 'b', 'c', 'd'] 

Die ersten vier Zeilen des Ergebnisses ist das Ergebnis des ‚print (Pfad)‘ in Zeile 4 des Codes. Aber Zeile 5, 6 und 7 ist das Ergebnis von 'Druck (Pfad)' in Zeile 17 des Codes.

Meine Frage ist warum die Liste des Pfades jedes Mal um einen Eckpunkt abnimmt?

Ich habe versucht, seine Lösung für 2 Tage zu finden. Ich bin in Foren gegangen, habe die Dokumentation über Rekursion gelesen und Videos angeschaut. Aber, kein Glück.

Ich wäre dankbar, wenn jemand antworten kann.

Answer 1

Zuerst werde ich nur eine Erklärung geben, was Backtracking bedeutet. Ich habe auch diese Antwort here gepostet.

Rekursion bedeutet, dass die Funktion innerhalb derselben Funktion aufgerufen wird. Nun, was passiert, wenn die Funktion einen Aufruf an sich selbst findet.Stellen Sie sich vor, dass eine neue Seite geöffnet wird und die Kontrolle von der alten Seite auf diese neue Seite an den Anfang der Funktion übertragen wird. Wenn die Funktion auf dieser neuen Seite erneut auf den Anruf trifft, öffnet sich eine weitere Seite und auf diese Weise neue Seiten bleib neben der alten Seite auf. Beachten Sie, dass alle lokalen Variablen nur im Bereich der jeweiligen Seiten enthalten sind. Das heißt, wenn Sie auf den Wert auf der vorherigen Seite zugreifen möchten, übergeben Sie ihn entweder an die Funktion in Parametern oder machen Sie die Variable global.

Die einzige Möglichkeit, zurück zu gehen, ist die Verwendung der Return-Anweisung. Wenn die Funktion darauf trifft, geht das Steuerelement von der neuen Seite zurück zur alten Seite derselben Zeile, von wo es aufgerufen wurde, und beginnt, was auch immer unter dieser Zeile ausgeführt wird. Hier beginnt das Backtracking. Um Probleme wie das erneute Eingeben von Daten zu vermeiden, müssen Sie in der Regel nach jedem Aufruf der Funktion eine Return-Anweisung eingeben.

Jetzt in Ihrem Code,

def find_path(graph,start,end,path=[]): 
    path = path + [start] 
    #Just a Test 
    print(path) 

    if start == end: 
     return path 

    if start not in graph: 
     return None 

    for node in graph[start]: 
     if node not in path: 
      new_path = find_path(graph,node,end,path) <---- when function returns it will start executing from here again. 
     if new_path: 
      #Just a test 
      print(path) 
      return new_path 

Und beachten Sie, dass Ihre path Variable nicht eine globale Variable ist. Es ist ein Einheimischer. Dies bedeutet, dass Sie jedes Mal, wenn Sie es aufrufen, zurückgesetzt werden. Um dies zu vermeiden, übergeben Sie den Pfadwert in den Funktionsparametern (zuletzt) ​​erneut.

Also schließlich, wenn die Funktion zurückkehrt, nachdem sie d gefunden hat, kehrt sie zum vorherigen Zustand zurück, in dem die Pfadvariable nur a, b, c enthält. das drucken Sie aus.

Edit: - Nur für den Fall, dass jemand Einwände, meine Erklärung der Rekursion mit Seiten ist rein nicht-technische, wenn Sie wissen wollen, wie es wirklich passiert, dann müssen Sie über Aktivierung Datensatz lesen und wie es alle drückt Zustand auf einen Stapel

Answer 2

Dies liegt daran, dass die Rekursion Ergebnisse von "innersten" bis "äußersten" Aufrufen liefert. Das ist die erste Zeile 17 print Anweisung tritt von der tiefsten Rekursionsebene, wo der Pfad die meisten Knoten hat. Nachdem diese Ebene zurückgegeben wurde, wird die nächste Ebene "nach oben" gedruckt (ein Knoten weniger im Pfad). Beachten Sie, dass Ihre print Funktion nach der rekursive Aufruf an kommt.

Sie können es visualisieren, wie folgt:

find_path(..., path=['a']) # Recursion level 1. 
| 
| find_path(..., path=['a', 'b']) # Recursion level 2. 
| | 
| | find_path(..., path=['a', 'b', 'c']) # Recursion level 3. 
| | print(path) # Prints ['a', 'b', 'c']. 
| | return # Return from level 3. 
| | 
| print(path) # Prints ['a', 'b']. 
| return # Return from level 2. 
| 
print(path) # Prints ['a']. 
return # Return from level 1. 

Wenn Sie die einzelnen (Teil-) Pfade in „Erhöhung“, um gedruckt werden, dann können Sie einfach legen Sie die print Funktion vor der rekursive Aufruf zu .

Es ist die Variable, die den rekursiv gefundenen Pfad enthält, während path nur den Pfad zum aktuellen Knoten enthält.

Übrigens könnte die if new_path:-Klausel fehlschlagen, wenn der vorherige if-Zweig noch nicht eingegeben wurde, weil dann nicht definiert ist.

Answer 3

1) die find_path Verfahren zuerst mit a als Startknoten, setzt den Pfad als ['a'] und ruft die Methode mit find_pathb als Startknoten vor dem Druckweg auf Leitung 17

aufgerufen 2) Der Aufruf an Methode mit b als Startknoten se ts den Pfad als ['a','b'] und ruft die Methode mit find_pathc als Startknoten, bevor Pfaddrucken auf Leitung 17.

3) Der Aufruf von find_path Methode mit c als Startknoten stellt den Pfad als ['a','b','c'] und ruft die Methode find_path mit d als Startknoten vor

4) um den Anruf zu find_path Methode mit d als Startknoten stellt den Pfad als ['a','b','c','d'] druckt auf es Leitung 4 und kehrt Pfad auf 17. Zeile gedruckt wird.

5) Jetzt ist es auf Leitung 14 kehrt in der Ausführung der Methode find_path mit c als Startknoten (der den Pfad als ['a','b','c'] gesetzt hatte, wie in Punkt 3) erwähnt, und druckt Pfad auf der Leitung 17 (die Linie 5. ist Ihr Ergebnis) und kehrt zurück.

6) Dies gibt auf der Leitung 14 in der Ausführung der Verfahren find_path mit b als Startknoten (der den Pfad als ['a','b'] gesetzt hatte gemäß Punkt 2) und druckt Pfad auf der Leitung 17 (die Linie 6. Ihre ist Ergebnis) und gibt zurück.

7) Dies gibt auf der Leitung 14 in der Ausführung der Verfahren find_path mit a als Startknoten (der den Pfad als ['a'] gesetzt hatte, wie in Punkt 1 erwähnt) und druckt Pfad auf der Leitung 17 (die Linie 6. Ihre ist Ergebnis) und gibt zurück.

Sie können es als LIFO vorstellen (Last In First Out)