Depth-First Search, without Recursion
First of all, what is Depth-First Search? Depth-First Search is a recursive algorithm to “search” through all of the nodes in a graph. How it works is like so: Starting off with a node, we mark it as visited, then for each of its neighbors that is not visited, we call depth first search on them.
We can also extend the algorithm to have an outer for loop that iterates through nodes in a graph calling DFS on them if they have not been visited yet. This will allow the algorithm to visit every single node in a graph, even if they are not connected, or if some nodes are not reachable from the others. Depth-first search is a remarkably simple algorithm, but it has one problem, the thing that makes it stands out: Recursion. The depth to which the algorithm recurses can overwhelm many machines and can be a headache to deal with when solving coding questions, like those on HackerRank. Therefore, we must find a way to not use recursion, in an algorithm that is known for recursion, indeed a mind-boggling problem.
Non-Recursive Depth First Search
When we think about the special property of the depth first search, we often think about the order in which it looks at the nodes. Specifically, we might notice that it searches deeper and deeper along one path until it cannot go any deeper, and then starts to backtrack, and searches from the next deepest node, repeating this process. It does this until there are not any more nodes to search.
Recursion captures this structure perfectly, as calling itself on a neighbor essentially focuses on that neighbor and not other calls can proceed until that “line” of recursion has been completed. However, we must remember that recursion results in a function call stack, and so a stack captures the exact same structure!
Therefore, it is natural for us to use our own stack in depth-first search, and imitate the spirit and structure of recursion. What we would do basically is to maintain our own stack and use a process very similar to the original depth first search. At the beginning, we would push the node we are given into the stack. Then we would iterate until the stack is empty. At each iteration, we pop out a node from the stack, check whether it has been visited, visit it, and put all of its neighbors that have not been visited into the stack.
This perfectly captures DFS, as nodes that are discovered most recently would be searched first. However, there is a problem: our algorithm would examine the neighbors of a node in reverse order as the neighbors are pushed in. To solve this issue (if it matters), all we need to do is just push neighbors in reverse order as we would do in normal DFS. Specifically, we could change the code in line 9 to say:
for neighbor in current.neighbors[::-1]:
That way, the stack will naturally pop it in the correct order.
The benefits of using an iterative version of DFS extend beyond not exceeding recursion limits. It also makes DFS fit in better with other algorithms, and provides a link between it, and its closest friend, BFS.
DFS’s relationship to BFS
An interesting relationship to note is that our new version of DFS closely resembles the other classical searching algorithm, BFS. Our iterative version of DFS reveals a fundamental relationship between BFS and DFS just as fundamental as between stacks and queues, that was previously masked by recursion.
Conclusion
The recursion involved in DFS is one of the elements that distinguish DFS and its status as an algorithm, but we saw how easily we can remove recursion. This helps us avoid passing max recursion depth limits, helps us understand DFS better, and also helps us draw some connections between it and BFS. All in all, the non-recursive version of DFS highlights important aspects of DFS that we could have otherwise missed. The next time you are doing a coding question, you won’t have to worry about recursion.
