Jak działają funkcje rekursywne wewnątrz pętli for?

Question

Jestem całkiem nowy w "funkcjach rekursywnych". Tak więc próbuję objaśnić, dlaczego używamy funkcji rekursywnych i jak działają funkcje rekursywne i myślę, że mam dość dobre zrozumienie.

Dwa dni temu próbowałem rozwiązać najkrótszy problem z trasą. Mam poniższy wykres (jest w Pythonie):

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

Po prostu staram się znaleźć drogę, a nie najkrótszą path.So, oto kod:

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

Moja początkowa wierzchołek to "a", a końcowy wierzchołek to "d".

W czwartym wierszu właśnie wydrukowałem "ścieżkę", aby zobaczyć, gdzie idzie ścieżka.

W linii 17 wydrukowałem również "ścieżkę", ponownie tylko do przetestowania. A oto wynik:

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

Pierwsze cztery wiersze wyniku to wynik "print (path)" na linii 4 kodu. Ale wiersz 5, 6 i 7 jest wynikiem "print (path)" w linii 17. kodu.

Moje pytanie brzmi, dlaczego lista ścieżek maleje o jeden wierzchołek za każdym razem?

Próbowałem znaleźć rozwiązanie na 2 dni. Poszedłem na fora, przeczytałem dokumentację o rekursji i obejrzałem filmy. Ale bez powodzenia.

Byłbym wdzięczny, gdyby ktoś mógł odpowiedzieć.

Answer 1

Najpierw zamierzam wyjaśnić, co oznacza wycofanie. Wysłałem również tę odpowiedź: here.

Rekursja oznacza wywołanie funkcji z tej samej funkcji. Teraz dzieje się tak, gdy funkcja napotyka na siebie.wyobraź sobie, że otwiera się nowa strona, a sterowanie przechodzi ze starej strony na tę nową stronę na początek funkcji, gdy funkcja ponownie napotka połączenie na tej nowej stronie, następna strona otwiera się obok niej iw ten sposób nowe strony nadal pojawiają się obok starej strony. Zwróć uwagę, że wszystkie zmienne lokalne są tylko w zasięgu ich stron. To znaczy, jeśli chcesz uzyskać dostęp do wartości z poprzedniej strony, możesz przekazać ją do funkcji w parametrach lub ustawić zmienną globalną.

Jedynym sposobem na powrót jest użycie instrukcji return. Kiedy funkcja go napotka, sterowanie przechodzi z nowej strony z powrotem na starą stronę w tym samym wierszu, z którego została wywołana i rozpoczyna wykonywanie tego, co znajduje się poniżej tej linii. Tu zaczyna się nawrót. Aby uniknąć problemów, takich jak podawanie danych ponownie, gdy są wypełnione, zazwyczaj musisz umieścić zwrotne oświadczenie po każdym wywołaniu funkcji.

Teraz w kodzie,

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 

I pamiętać, że zmienna path nie jest zmienną globalną. To lokalny. Oznacza to, że za każdym razem, gdy wywołasz jego reset. Aby tego uniknąć, ponownie podajesz wartość ścieżki w parametrach funkcji (w ostatnim).

W końcu, gdy funkcja zwraca po znalezieniu d, powraca do poprzedniego stanu, w którym zmienna ścieżki ma tylko a, b, c. to właśnie wydrukujesz.

Edycja: - Na wypadek, gdyby ktokolwiek się sprzeciwił, moje wyjaśnienie rekursji przy użyciu stron jest czysto nietechniczne, jeśli chcesz się dowiedzieć, jak to naprawdę się dzieje, musisz przeczytać o zapisie aktywacji i jak popycha to wszystko stan na stosie

Answer 2

Dzieje się tak, ponieważ rekurencja daje wyniki od "najgłębszego" do "zewnętrznego". Jest to pierwsza instrukcja 17 print z najgłębszego poziomu rekurencji, w którym ścieżka ma najwięcej węzłów. Po powrocie tego poziomu drukowany jest następny poziom "w górę" (jeden węzeł mniej w ścieżce). Zauważ, że twoja funkcja print przychodzi po rekurencyjnym wywołaniu do find_path.

Można wyobrazić go w następujący sposób:

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. 

Jeśli chcesz pojedyncze (pod) ścieżki mają być drukowane w „rośnie”, aby następnie można po prostu umieścić print funkcję przed wywołanie rekurencyjne do find_path.

Jest to zmienna new_path, która przechowuje rekursywnie znalezioną ścieżkę, a path po prostu przechowuje ścieżkę do bieżącego węzła.

Sytuacja, w której klauzula if new_path: może się nie udać, jeśli poprzednia gałąź if nie została jeszcze wprowadzona, ponieważ wtedy new_path jest niezdefiniowana.

Answer 3

1) metoda find_path najpierw nazwie z a jako węzła początkowego, który wyznacza ścieżkę ['a'] i wywołuje metodę find_path z b jako węzła początkowego przed wydrukowaniem ścieżkę na linii 17.

2) Wywołanie metody find_path z b jako se węzła początkowego ts ścieżce jako ['a','b'] i wywołuje metodę find_path z c jako węzła początkowego przed wydrukowaniem ścieżkę na linii 17.

3) Wezwanie do find_path metody z c jako węzła początkowego ustawia ścieżkę ['a','b','c'] i wywołuje metodę find_path z d jako węzła początkowego przed wydrukowaniem ścieżki na linii 17.

4) wywołanie find_path sposobu z d jako węzeł początkowy ustawia ścieżki jako ['a','b','c','d'] drukowanie na linii 4 i powraca.

5) Teraz zwraca się na linii 14 w wykonaniu sposobu find_path z c jako węzła początkowego (który ustawić ścieżkę jako ['a','b','c'] wymienione w punkcie 3) i drukuje ścieżkę na linii 17 (który jest linia 5-TE twój wynik) i zwraca.

6) powróci na linii 14 w wykonaniu sposobu find_path z b jako węzła początkowego (który ustawić ścieżkę jako ['a','b'] wymienione w punkcie 2) i drukuje ścieżkę na linii 17 (który jest linia 6th od swojej wynik) i zwraca.

7), to zwraca się na linii 14 w wykonaniu sposobu find_path z a jako węzła początkowego (który ustawić ścieżkę jako ['a'] wymienione w punkcie 1) i drukuje ścieżkę na linii 17 (który jest linia 6th od swojej wynik) i zwraca.

Można to sobie wyobrazić jako LIFO (Last In First Out)