How does return statement works in a recursive function?

Question

I found a code to check whether given graph is a tree

# 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")

Stack Trace for the above code

During the fourth iteration i.e 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

When returned 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)_|  }
                               )              

When for instance, returned True(for experimentation)

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<______________|

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.
Can anyone clarify my doubt.

Thanks in advance for any help

Answer 1

'return' always terminates the current activation of a function and returns control to the point at which it was called.

In a recursive function, then, you can imagine the activations as being 'nested' one inside the other. Number them 0, 1, … if we're in activation N of isCyclicUtil, and we call isCyclicUtil, then that creates activation N+1.

When a return is execution in activation N+1, it returns precisely to the call in activation N.

This is no different to non-recursive functions. If function X calls function Y, and function Y executes 'return', then control returns to function X (immediately after the point at which Y was called).

For recursive calls, X and Y are the same function, but the rules for call and return have not changed.

In your particular case, the recursive call is in the middle of a for-loop, so that's where control returns to when the inner call returns. And if the value returned from the inner call is true, then the outer call immediately returns to its caller, thus terminating the loop.

So returns always return to the same place, and it's what happens afterwards (what the immediate caller does with the returned value) that makes the difference.

---

I added lots of print statements to your code (very hacky, not cleanly done)

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  

Having done that, I see what I should have seen all along. You think that when the inner call returns True then it somehow returns all the way out. But what actually happens is that control is (of course) returned to the immediate caller, which then (because the return is true) then returns to its immediate caller, and so on all the way out.

The main portion of the annotated code:

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