python-3.x - return 语句如何在递归函数中工作？

Question

我找到了一个代码来检查给定的图形是否是一棵树

# Python Program to check whether 
# a graph is tree or not 

from collections import defaultdict 

class Graph(): 

    def __init__(self, V): 
        self.V = V 
        self.graph = defaultdict(list) 

    def addEdge(self, v, w): 
        # Add w to v ist. 
        self.graph[v].append(w) 
        # Add v to w list. 
        self.graph[w].append(v) 

    # A recursive function that uses visited[] 
    # and parent to detect cycle in subgraph 
    # reachable from vertex v. 
    def isCyclicUtil(self, v, visited, parent): 

        # Mark current node as visited 
        visited[v] = True

        # Recur for all the vertices adjacent 
        # for this vertex 
        for i in self.graph[v]: 
            # If an adjacent is not visited, 
            # then recur for that adjacent 
            if visited[i] == False: 
                if self.isCyclicUtil(i, visited, v) == True: 
                    return True

            # If an adjacent is visited and not 
            # parent of current vertex, then there 
            # is a cycle. 
            elif i != parent: 
                return True

        return False

    # Returns true if the graph is a tree, 
    # else false. 
    def isTree(self): 
        # Mark all the vertices as not visited 
        # and not part of recursion stack 
        visited = [False] * self.V 

        # The call to isCyclicUtil serves multiple 
        # purposes. It returns true if graph reachable 
        # from vertex 0 is cyclcic. It also marks 
        # all vertices reachable from 0. 
        if self.isCyclicUtil(0, visited, -1) == True: 
            return False

        # If we find a vertex which is not reachable 
        # from 0 (not marked by isCyclicUtil(), 
        # then we return false 
        for i in range(self.V): 
            if visited[i] == False: 
                return False

        return True

# Driver program to test above functions 
g1 = Graph(5) 
g1.addEdge(0, 1) 
g1.addEdge(1, 2) 
g1.addEdge(2, 3) 
g1.addEdge(2, 4) 
g1.addEdge(0, 4)
if (g1.isTree()):
    print("Graph is a tree")
else:
    print("Graph is not a tree")

上述代码的堆栈跟踪

在第四次迭代期间，即 v = 3，parent = 2

def isCyclicUtil(self, v, visited, parent): #(3,visited,2)
        visited[v] = True
        for i in self.graph[v]: #when the for loop breaks
            if visited[i] == False: 
                if self.isCyclicUtil(i, visited, v) == True: 
                    return True 
            elif i != parent: 
                return True
        return False #Why is that the return condition returns to the previous for loop when the
                     #return statement is False and when it is True it returns to the calling function

返回时为 False

#vi is visited #cy is iscycleutil()
                                             _ _ _ _ _ _ _ _ _ _ 
0,vi,-1       _>(1,vi,0)     _>(2,visited,1)|   _>(3,vi,2)      |
{            |  {           |  {            |  |  {             |
  cy(i,vi,v)_|   cy(i,vi,v)_|   for loop <__|  |   return False_|
}               }                   cy(i,vi,v)_|  }
                               )              

例如，当返回 True（用于实验）

0,vi,-1       _>(1,vi,0)     _>(2,visited,1)    _>(3,vi,2)      
{            |  {           |  {               |  {             
  cy(i,vi,v)_|   cy(i,vi,v)_|   for loop       |   return True__
}               }                   cy(i,vi,v)_|  }             |
                               )      return True<______________|

为什么return语句为False时返回条件返回前一个for循环，为True时返回调用函数。
谁能澄清我的疑问。

提前感谢您的帮助

标签： python-3.xrecursiongraph

Answer 1

'return' 总是终止函数的当前激活并将控制权返回到调用它的点。

那么，在递归函数中，您可以将激活想象为一个“嵌套”在另一个内部。将它们编号为 0、1、……如果我们在 isCyclicUtil 的激活 N 中，并且我们调用 isCyclicUtil，那么这将创建激活 N+1。

当在激活 N+1 中执行返回时，它精确地返回到激活 N 中的调用。

这与非递归函数没有什么不同。如果函数 X 调用函数 Y，并且函数 Y 执行“return”，则控制权返回到函数 X（紧接在调用 Y 的点之后）。

对于递归调用，X 和 Y 是同一个函数，但是调用和返回的规则没有改变。

在您的特定情况下，递归调用位于 for 循环的中间，因此当内部调用返回时，控制返回到该位置。如果内部调用返回的值为真，那么外部调用立即返回给它的调用者，从而终止循环。

所以返回总是返回到同一个地方，这就是之后发生的事情（直接调用者对返回值所做的事情），这会有所不同。

---

我在您的代码中添加了很多打印语句（非常hacky，没有干净地完成）

isCyclic called with v=0 at depth 0  
 loop at depth 0, i=1, v=0, visited[i]=False  
isCyclic called with v=1 at depth 1  
 loop at depth 1, i=0, v=1, visited[i]=True  
 loop at depth 1, i=2, v=1, visited[i]=False  
isCyclic called with v=2 at depth 2   
 loop at depth 2, i=1, v=2, visited[i]=True   
 loop at depth 2, i=3, v=2, visited[i]=False  
isCyclic called with v=3 at depth 3  
 loop at depth 3, i=2, v=3, visited[i]=True  
at end, return from depth 3  
 nested call returned False  
 loop at depth 2, i=4, v=2, visited[i]=False  
isCyclic called with v=4 at depth 3  
 loop at depth 3, i=2, v=4, visited[i]=True  
 loop at depth 3, i=0, v=4, visited[i]=True  
not parent, returning from depth 3  
 nested call returned True  
returning from depth 2  
 nested call returned True  
returning from depth 1  
 nested call returned True  
returning from depth 0  

这样做之后，我看到了我应该一直看到的东西。您认为当内部调用返回 True 时，它​​会以某种方式一直返回。但实际发生的是控制权（当然）返回给直接调用者，然后（因为返回为真）然后返回给它的直接调用者，依此类推。

注释代码的主要部分：

def isCyclicUtil(self, v, visited, parent):
    global depth
    depth = depth+1

    print("isCyclic called with v=%d at depth %d" % (v, depth))

    # Mark current node as visited
    visited[v] = True

    # Recur for all the vertices adjacent
    # for this vertex
    for i in self.graph[v]:
        print(" loop at depth %d, i=%d, v=%d, visited[i]=%s" % (depth,i,v, visited[i]))

        # If an adjacent is not visited,
        # then recur for that adjacent
        if visited[i] == False:
            temp = self.isCyclicUtil(i, visited, v)
            print(" nested call returned %s" % temp)
            if temp == True:
                print("returning from depth %d" % depth)
                depth = depth-1
                return True

        # If an adjacent is visited and not
        # parent of current vertex, then there
        # is a cycle.
        elif i != parent:
            print("not parent, returning from depth %d" % depth)
            depth = depth-1
            return True

    print("at end, return from depth %d" % depth)
    depth = depth-1
    return False