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

We can't return any value, because if it's False, the for loop breaks and never finds the True that may be later..

Example:

def divisible_by_five_A():
    for n in range(100):
        if n and not n % 5:
            return n, 1

divisible_by_five_A()
# O: 5, 1

vs

def divisible_by_five_B():
    for n in range(100):
        return n, (n and not n % 5)

divisible_by_five_B()
# O: 0, 0

Answer 2

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

Answer 3

Yes, the search needs to continue if depthFirst(adjNode, soughtValue, visitedNodes) returns False. Only when you've found the sought value in that part of the graph then you can return True for your search.

If you were to replace that with return depthFirst(adjNode, soughtValue, visitedNodes) then you'll only search for the value in that part of the graph (starting from that adjacent node) but you won't continue your search in case the value isn't found there.