Course contentsShow
← Computer Science
Lesson 710 of 2,87217. Graph Traversal AlgorithmsFree lesson

DFS Recursive Implementation

Implement DFS using recursion with visited tracking and neighbor exploration.

DFS Recursive Implementation

You'll learn how to implement depth-first search using recursion with proper visited tracking.

The Core Idea

Depth-First Search (DFS) explores a graph by going as deep as possible down one path before backtracking. The recursive approach is beautifully simple: visit a node, mark it as visited, then recursively visit each unvisited neighbor. The call stack naturally handles the "backtracking" for you when each recursive call completes.

Think of exploring a cave system: you follow one tunnel all the way to its end, then come back and try the next unexplored tunnel. Recursion is perfect for this because each tunnel exploration is the same process at a smaller scale.

Implementation Structure

The recursive DFS function needs three key elements:

  1. Base case: If the current node is already visited, return immediately
  2. Mark visited: Track the current node to avoid cycles
  3. Recursive exploration: Call DFS on each unvisited neighbor

Here's the pattern in pseudocode:

function dfs(node, visited):
    mark node as visited
    process node (print, count, etc.)
    
    for each neighbor of node:
        if neighbor not in visited:
            dfs(neighbor, visited)

The visited set prevents infinite loops in graphs with cycles. Each recursive call explores one branch completely before the previous call continues to the next neighbor.

The recursion depth equals the longest path explored from the starting node, which determines the space complexity from the call stack.

Key Takeaway: Recursive DFS elegantly explores graphs depth-first by marking nodes visited and recursively processing unvisited neighbors, with the call stack managing backtracking automatically.