中間結果が再帰DFS関数になる - Python

Question

私は基本的に、この例では再帰をよく理解しようとしています。基本ルートノードに接続されているすべてのノードを返す次のDFSアルゴリズムを見てみましょう。この場合の「グラフ」は、頂点間の辺のタプルのリストとして定義されます。例えば

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 

グラフは

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

た場合、ノード0から始まるの結果は、私がこのような場合には好奇心だが、これが結果であるということである

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

だろう再帰呼び出しのうちの1つのみからの「戻り値」を返します。明らかに、コードは意図したとおりに動作し、結果はうまくいきますが、中間の「戻り値」がどこにあるのか不思議です。我々は右returnステートメントの前に追加print文と同じ機能を実行すると例えば、私たちは次のような出力が得られます。

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] 

それでは、どのようにPythonは関数の実際の出力であるこれらのいずれか知っているのですか？それはちょうど最後のものですか？あなたは再帰関数を呼び出し、このラインで

Answer 1

：ネストされたコールの戻り値が終わるところ

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

です。この値を変数に代入するわけではないので、Pythonは次の反復に行くとすぐにそれを忘れてしまいます。 。

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

（例外は印刷されませんあなたの最初の呼び出しによって返される値であるあなたがそう：あなたは、次のprint文を使用しての上に印刷したものとして、あなたは（ほぼ）同じ出力を取得する必要があります上記よりも[0, 1, 2]の行が1つ少ないはずです。）