Depth first search: return values

Question

I was reading about depth first search (here) and was wondering why we don't return the value of the recursive call. This might sound strange, so here's the code with the line in question commented:

def depthFirst(node, soughtValue, visitedNodes):
    if node.value == soughtValue:
        return True

    visitedNodes.add(node)
    for adjNode in node.adjacentNodes:
        if adjNode not in visitedNodes:
            if depthFirst(adjNode, soughtValue, visitedNodes): # why this?
              return True

    return False

My question: would replacing:

if depthFirst(adjNode, soughtValue, visitedNodes):
    return True

with

return depthFirst(adjNode, soughtValue, visitedNodes):

cut the search short by evaluating to False prematurely? The lines in question seems to be saying follow the current adjNode and see if it leads to a solution; if it does, we'll get a series of True statements returned all the way to the beginning of the search (our current adjNode) from the leaf; this happens all the way to the root (the start of our search and the first recursive call). Only then we can say we've found a valid path and return 'True'.

It seems as though the first return statement triggers the chain of 'True' statements and we leave the search inside the loop. Am I correct? There's a lot going on and any further explanation would be greatly appreciated.

Answer 1

Suppose we have the following graph:

            1 ——— 2
            |     
            4 ——— 5 ——— 6
            |     |     |     
            7 ——— 8 ——— 9

Where soughtValue is node 9. Starting from node 1 as source:

   wrong code:
   ===========
   dfs(1,9,…)                          dfs(2,9,…)  
       …                                    …
       // neighbors                        // neighbors          
       return dfs(2,9,…)  <———|            NO return dfs(1,9,…) as 1 has been visited
       return dfs(4,9,…)      |             
                              |             
                              |            so return false
                              |             |
                              |-------------|

   result
   dfs(1,9,…) terminates with a false even without going to dfs(4,9,…)



   correct code:
   ============
   dfs(1,9,…)                  dfs(2,9,…)     
        …                           …
       // neighbors                // neighbors                
       if (dfs(2,9,…)) <———|       NO if dfs(1,9,…) as as 1 has been visited
            return true    |           return true
                           |
       if (dfs(4,9,…))     |    
            return true    |    
                           |             
                           |        so return false
                           |             |
                           |-------------|

   result
   dfs(1,9,…) doesn't terminate and does continue to other neighbors (i.e., dfs(4,9,…)) and so on until we reach the soughtValue 9 and return true