Introduction

Depth-first search explores one path in a graph as far as possible before backtracking. Recursion is a natural way to implement that behavior because the call stack already gives you the same last-in, first-out structure that DFS needs.

How Recursive DFS Works

A recursive DFS usually does three things for each node:

• mark the node as visited
• process the node
• recursively visit each unvisited neighbor

The visited set is the important part for general graphs. Without it, a cycle can send the recursion around the same loop forever.

The graph can be stored in several ways, but an adjacency list is the most common choice because it is easy to traverse and efficient for sparse graphs.

A Simple Python Implementation

The example below performs DFS on a graph stored as a dictionary of neighbor lists. The function returns the visitation order so the result is easy to inspect.

1graph = {
2    "A": ["B", "C"],
3    "B": ["D", "E"],
4    "C": ["F"],
5    "D": [],
6    "E": ["F"],
7    "F": [],
8}
9
10
11def dfs(graph, node, visited=None, order=None):
12    if visited is None:
13        visited = set()
14    if order is None:
15        order = []
16
17    visited.add(node)
18    order.append(node)
19
20    for neighbor in graph.get(node, []):
21        if neighbor not in visited:
22            dfs(graph, neighbor, visited, order)
23
24    return order
25
26
27print(dfs(graph, "A"))

The output is one valid depth-first traversal order:

['A', 'B', 'D', 'E', 'F', 'C']

DFS order depends on neighbor order. If the adjacency lists were arranged differently, the traversal could visit the same nodes in another valid depth-first order.

Why Recursion Feels Natural Here

Each recursive call says, in effect, "visit this node and finish its entire subtree or reachable branch before returning." That mirrors the core idea of DFS directly.

On a tree, recursive DFS is especially clean because there are no cycles unless you explicitly model parent links. On a general graph, the extra visited set is what keeps the recursion safe.

The time complexity is O(V + E) because each vertex and edge is examined at most once. The extra space is O(V) for the visited set plus the recursion stack in the worst case.

When Recursion Is Not Ideal

Recursive DFS is elegant, but it is not always the best operational choice. A very deep graph can exceed the language's recursion limit or stack size. In Python, for example, an iterative DFS with an explicit stack is safer for very deep traversals.

Even so, recursion is still the clearest way to learn the algorithm and is perfectly fine for moderate graph depths, tree traversals, interview practice, and many everyday graph problems.

Common Pitfalls

• Forgetting the visited set when the graph can contain cycles.
• Using a mutable default argument such as visited=set() or order=[], which reuses state across calls.
• Assuming DFS has only one correct order. The exact order depends on neighbor ordering.
• Recursing too deeply on a huge or badly shaped graph and hitting the recursion limit.
• Confusing tree traversal with graph traversal. Trees usually do not need a visited set, but graphs usually do.

Summary

• Recursive DFS works by visiting a node, then recursively exploring each unvisited neighbor.
• A visited set is essential for graphs that may contain cycles.
• Adjacency lists are a convenient representation for recursive DFS.
• The algorithm runs in O(V + E) time.
• Recursion is elegant and simple, but iterative DFS is safer for very deep graphs.