DFS: Recursive and Iterative
24 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Breadth-first search spreads wide. Depth-first search digs deep. It is the base of component counting, cycle detection and every backtracking search, and in Python it comes in two forms: recursive and with a stack.
Go deep first
Depth-first search (DFS) follows one path as far as possible, then goes back and tries the next branch. It uses recursion or an explicit stack, and visits every reachable node once.
In a maze you follow one corridor to its end, and only then back up to try the next turn. Depth-first search explores a graph the same way: it goes as far as it can, then backtracks.
Recursive DFS
Each call visits one node, marks it, and calls itself for every unseen neighbour. The call stack remembers where to come back to.
def dfs(graph, node, seen, order): seen.add(node) order.append(node) for nxt in graph[node]: if nxt not in seen: dfs(graph, nxt, seen, order)Example 1 · Recursive DFS order
from collections import defaultdict
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)
def dfs(graph, node, seen, order): seen.add(node) order.append(node) for nxt in graph[node]: if nxt not in seen: dfs(graph, nxt, seen, order)
order = []dfs(graph, 0, set(), order)print(order)[0, 1, 3, 2, 4]
What this code does
- From 0 the search goes to 1, then 3, then 2 (a neighbour of 3), and finally 4.
- It went deep along 0, 1, 3 before it came back for 2.
Example 2 · Is there a path?
from collections import defaultdict
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)
def has_path(graph, node, goal, seen): if node == goal: return True seen.add(node) for nxt in graph[node]: if nxt not in seen and has_path(graph, nxt, goal, seen): return True return False
print(has_path(graph, 0, 4, set()))print(has_path(graph, 0, 9, set()))True False
What this code does
- The function returns True as soon as one branch finds the goal, and the other branches are skipped.
- Node 9 is not in the graph, so every branch ends and the answer is False.
The set seen is shared by all calls, so it works as one memory for the whole search. Time is O(n + m) and the stack can go n calls deep.
Iterative DFS with a stack
A Python list works as a stack: append pushes and pop takes the newest item. Replace the call stack with your own and the same search needs no recursion.
def dfs_iter(graph, start): seen = set() stack = [start] order = [] while stack: node = stack.pop() if node in seen: continue seen.add(node) order.append(node) for nxt in reversed(graph[node]): if nxt not in seen: stack.append(nxt) return orderExample 3 · Iterative DFS order
from collections import defaultdict
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)
def dfs_iter(graph, start): seen = set() stack = [start] order = [] while stack: node = stack.pop() if node in seen: continue seen.add(node) order.append(node) for nxt in reversed(graph[node]): if nxt not in seen: stack.append(nxt) return order
print(dfs_iter(graph, 0))[0, 1, 3, 2, 4]
What this code does
- The result is the same as the recursive version because neighbours are pushed in reverse.
- A list as a stack uses O(1) per push and pop and never hits the recursion limit.
Here a node is marked when it is taken out, since it may be pushed more than once. reversed makes the order match the recursive version.
Python's recursion limit
Python allows about 1000 nested calls by default and then raises RecursionError. A path of 100000 nodes breaks recursive DFS, so for large inputs write the iterative version. In an interview, say which one you chose and why.
Example 4 · Recursion limit versus a stack
def build_chain(n): graph = {i: [i + 1] for i in range(n - 1)} graph[n - 1] = [] return graph
def depth_recursive(graph, node): return 1 + max((depth_recursive(graph, n) for n in graph[node]), default=0)
def depth_iterative(graph, start): count, stack = 0, [start] while stack: node = stack.pop() count += 1 stack.extend(graph[node]) return count
chain = build_chain(3000)try: print(depth_recursive(chain, 0))except RecursionError: print("RecursionError")print(depth_iterative(chain, 0))RecursionError 3000
What this code does
- A chain of 3000 nodes needs 3000 nested calls, more than the default limit, so the recursive version fails.
- The stack version visits all 3000 nodes with no trouble.
Example 5 · Backtracking: count all simple paths
from collections import defaultdict
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)
def count_paths(node, goal, on_path): if node == goal: return 1 total = 0 on_path.add(node) for nxt in graph[node]: if nxt not in on_path: total += count_paths(nxt, goal, on_path) on_path.remove(node) return total
print(count_paths(0, 4, set()))2
What this code does
- Here the node is removed again after its branch, so another path may use it. This is called backtracking.
- Two simple paths exist: 0, 1, 3, 4 and 0, 2, 3, 4. Counting every path can take exponential time.
Next step
Check your understanding
10 quick questions