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!