Résultats intermédiaires dans une fonction DFS récursive - Python

Question

J'essaie fondamentalement de mieux comprendre la récursivité avec cet exemple. Regardons l'algorithme DFS suivant qui renvoie tous les nœuds connectés au nœud racine de base. Le "graphe" dans ce cas est défini comme une liste de tuples d'arêtes entre sommets.

def dfs(graph,node,dfs_visited): 
    if node not in dfs_visited: 
     dfs_visited.append(node) 

     #find next node to go 
     potential_paths = [i for i in graph if node in i] 
     new_nodes = [node_ for path in potential_paths for node_ in 
        path if node_ !=node] 
     for n in new_nodes: 
      dfs(graph,n,dfs_visited) 
    return dfs_visited 

Par exemple, si le graphique était

graph = [(0, 1),(0, 2),(1, 2),(3, 4),(4,5)] 

le résultat de démarrage au niveau du noeud 0 serait

dfs(graph,0,[]) 
[0,1,2] 

Ce que je suis curieux de savoir dans ce cas est que cela est le résultat du "retour" d'un seul des appels récursifs. Évidemment, le code fonctionne comme je le souhaitais et je suis d'accord avec le résultat, mais je suis juste curieux de savoir où va l'intermédiaire "retourne". Par exemple, lorsque nous courons la même fonction avec une instruction d'impression ajouté juste avant la déclaration de retour, nous obtenons le résultat suivant:

dfs(graph,0,[]) 
returning [0, 1] 
returning [0, 1, 2] 
returning [0, 1, 2] 
returning [0, 1, 2] 
returning [0, 1, 2] 
returning [0, 1, 2] 
returning [0, 1, 2] 

Alors, comment Python savoir lequel d'entre eux est la sortie réelle de la fonction? Est-ce juste le dernier?

Answer 1

Dans cette ligne où vous appelez la fonction récursive:

for n in new_nodes: 
    dfs(graph,n,dfs_visited) 

est où la valeur de retour des extrémités imbriquer vers le haut. Vous n'attribuez cette valeur à aucune variable, aussi python l'oublie dès qu'il passe à l'itération suivante. Vous devriez obtenir (presque) la même sortie que ce que vous avez imprimé au-dessus en utilisant l'instruction d'impression suivante:.

for n in new_nodes: 
    ret = dfs(graph,n,dfs_visited) 
    print(ret) 

(L'exception est la valeur retournée par l'appel initial, qui ne sera pas imprimé Vous devrait avoir une ligne de moins de [0, 1, 2] que ci-dessus.)