Understanding recursion for Depth-First Search code?

Hi! I’m doing the Breadth-First Search algorithm and can’t really seem to understand how the recursion function works in this scenario.

def dfs(root, target):

  if root.value == target:

    return root

  for child in root.children:

    node_found = dfs(child, target)

    if node_found is not None:

      return node_found

  return None

From my understanding, if the root node is not the node that you want to find, it gets the first child of the root node. It then calls the function again to check whether the first child (child 1), now the new “root” node, equals the target value. If it still does not contain the target value, it goes through a recursion and finds the first child’s first child (child 1-1) and checks the value and so on and so forth.

Then I don’t really get it from here. Why would it ever reach the second if statement to check if node_found is not None, since the code will keep going down the tree until it has no more children? How would it reach the second or third child (e.g child 1-2 or 1-3)?

The whole thing is a bit of a blur since it appears to me that the recursion function just keeps being called without end and will never reach any of the other conditions without first bumping into another recursive function.

Any other resources to understand recursion better would also be greatly appreciated. Thanks!

1 Like

You could start with a very simple example just to track the flow, if you can do this with a few simple scenarios the overall picture might become clearer.

Imagine two nodes, the second of which contains the .value that you want. Apologies for the flaky notation, I don’t have time to fix it at the minute.

So you call dfs on the first node, we’ll call it N0. Does it have the right .value, no. So a loop starts looking into the children of N0

We start with the first child. We’ll name it N0-1. Here we call dfs(N0-1), a new item on the stack (lets name that function call S2). Now the if statement tests if N0-1 has the right .value, it does. So we return root which has the value of N0-1 (ending function call S2) back to the caller, S1.

This is subsequently assigned to node_found in the very first function on the stack, S1. We then test if node_found is not None, which is True because it is N2. We return this value, N0-1 ending the first call and returning the matching node.

Spin up similar scenarios, e.g. a single node N0 with two children, N1 & N2 each of which have a further child N1-1 and N2-1. The .value we want is at N2-1.

Follow the flow! Use pen & paper or something to track it if you like. If you really can’t follow it then a little debugging e.g. some logging/printing output can help.

2 Likes

I have a doubt!
Consider this example :

def dfs(root, target, path=()):
  path += (root,)

  if root.value == target:
    return path

  for child in root.children:
    path_found = dfs(child, target, path)

    if path_found is not None:
      return path_found

  return None
A
├─B
       ├─D
       └─E
└─C
       ├─F
       └─G

In this tree, if the target node we’re looking for is the node with value D. The call stack would be initialized with the first function call with the root node ( Node A ). The second function call added to the call stack would be that of Node B. The third function added would be the call to Node D. This was the node we were looking for. Hence, the call to Node D would return the path to it and get popped off from the call stack. My doubt here is, what happens to the remaining function calls in the call stack. Would they return None and get popped off? Won’t that change the value of path_found?

2 Likes

Thanks so much for the reply, I think I kind of get it now. It makes sense when I follow through it with a pen and paper after your explanation, but it’s still kinda iffy (like I get how it works but how do you even think of such solutions when coding the algorithms :frowning: it feels like something I can’t reproduce and can only follow).

It would also be very kind of you if you could answer kaushikcodes’ question :slight_smile:, i’m also quite curious. Thanks!

2 Likes

Consider what your return was when you found the correct root value. It would have been a path like '/A/B/C'. So your tests, if path_found is not None evaluate to True and return the path rather than None.

Here’s a hacky attempt to explain that-

dfs(A, target, path)
    path = '/A'
    if target: False
    for ...
        path_found = dfs(B, target, '/A')
            """Now in second function on stack"""
            path = '/A/B'
            if target: False
            for ...
                path_found = dfs(C, target, '/A/B')
                    """Now in third function on stack"""
                    path = 'A/B/C'
                    if target: True!
                    """Leave the third function"""
                    return path

                """Inside for loop of second function, test for empty_path"""
                if path_found not None: True
                """Path is not empty, it is 'A/B/C', leaving second function"""
                return path_found
        
        """Inside for loop of first function, test for empty_path"""
        if path_found not None: True
        """Path is not empty, it is 'A/B/C', leaving first function"""
        return path_found
1 Like

Thank you so much for your prompt reply. I get a better understanding now! Much appreciated!

1 Like

I think it’s like anything else which is unfamiliar, say functions themselves. You start by writing very simple functions that take a single argument and return a single value. Then you practice with that and add more steps and so on. For recursion it’s best to start with and master the early steps in the same way. Then you’ll start to spot things where you could use it and in time you’ll create more complex flows (there are loads of online examples if you want more practice).

After that you’ll probably be collaborating in a group and your lead tells you that your recursive solution is a very clever and beautiful example but the rest of the team don’t understand it. Consequently for the sake of long-term maintenance it has to go :laughing:.

1 Like