Depth-First Search

Depth-first search explores as deep as possible along one branch before backtracking. Frontier is a LIFO stack (or recursion).

Algorithm

``` function DFS(initial, goal): return dfs_helper(initial, [], {initial})

function dfs_helper(state, path, visited): if state is goal: return path for action in actions(state): next = transition(state, action) if next not in visited: visited.add(next) result = dfs_helper(next, path + [action], visited) if result: return result return None ```

Properties

• Complete: no on infinite state spaces (gets stuck going down infinitely deep branches). Yes on finite state spaces with cycle checking.
• Optimal: no — finds *a* solution, not the shortest.
• Time: $O(b^m)$ where $m$ is maximum depth. Can be much worse than $O(b^d)$ if $m \gg d$.
• Space: $O(bm)$ — only stores the current path and siblings at each level.

When DFS is the right call

• The state space is finite and reasonably bounded.
• You don't care about optimality.
• Memory is binding (BFS is too expensive).
• The structure of the problem favors deep exploration (mazes, certain combinatorial problems).

Iterative deepening

The best of both worlds: run DFS with depth limit 0, then 1, then 2, etc. Each iteration is cheap; you eventually find the shallowest solution. Total work is $O(b^d)$ — same as BFS — but space is $O(bd)$.

For uninformed search of a tree with shallow solutions, iterative deepening DFS is usually the right default. It's also the basis of IDA* (covered in the informed search section).

Pitfalls

• Without cycle detection, infinite loops are easy on graphs with cycles.
• "Picks one path and explores it fully" sounds appealing but means you can do enormous amounts of useless work if the solution is in a different subtree.
• Worst-case behavior depends on action ordering — try the most-promising-looking action first to avoid pathological cases.