## Definition **Depth-First Search (DFS)** is an [[Uninformed Search]] algorithm that expands the deepest unexplored node first. Implemented with a **LIFO stack** (or recursion). ## Algorithm ``` frontier ← LIFO stack with the initial state explored ← ∅ while frontier is non-empty: node ← pop(frontier) if isGoal(node.state): return path(node) explored.add(node.state) for each action a in A(node.state): child ← expand(node, a) if child.state not in explored: push(frontier, child) return failure ``` ## Properties - **Complete:** no, in infinite or cyclic state spaces. Add depth limits or cycle detection. - **Optimal:** no. - **Time:** $O(b^m)$ — can explore an entire branch before backtracking, where $m$ is the maximum depth. - **Space:** $O(bm)$ — only the current path plus siblings is stored. The big win. ## Why Space Wins While [[Breadth-First Search]] is $O(b^d)$ in memory, DFS stays linear in depth. For deep state spaces with many possible solutions at depth, this is decisive. ## Trade-offs - **Pro:** memory-efficient. - **Con:** can dive into infinite or very deep branches missing shallower goals. - **Mitigation:** **depth-limited DFS** caps depth at $\ell$; **iterative deepening** (see [[Iterative Deepening Search]]) wraps this in a loop that increases $\ell$ progressively. ## When to Use - Memory-constrained settings. - All solutions are at similar depth, or any solution will do. - Trees with no cycles (or cycle detection is cheap). ## Related - [[Uninformed Search]] - [[Breadth-First Search]] - [[Iterative Deepening Search]]