Depth-First Search and Iterative Deepening

1Depth-first search

Depth-first search expands the newest frontier node first — a LIFO stack — so it commits to one branch and goes one level deeper with every step, retreating only when the branch runs out of moves.

The memory bill is the whole attraction. DFS holds the current path plus the untried siblings hanging off it: with branching factor b and maximum depth m, that is O(b \cdot m) nodes against BFS's O(b^d) — a corridor instead of a wave. A path 100 deep at branching 10 is about a thousand held nodes, where a BFS level at that depth would hold more states than there are atoms to build the RAM from.

You have written DFS even if you never named it: any recursive traversal is depth-first, with the language's call stack as the frontier. That is also why deep recursion overflows — the stack is the memory bill made physical.

What DFS refuses to promise: the goal may sit two moves from the start while the search is forty deep in the wrong subtree, so the first path found can be needlessly long — finding a solution fast and finding a short solution are different jobs.

One cycle of the dive

1. DiveExpand the newest node and push its children; the search goes one level deeper each step.
2. Dead endThe current branch has no untried moves left and none of them was the goal.
3. BacktrackPop back to the most recent node with an untried sibling and dive again from there.

Coding lab. DFS visit order, by hand and by networkx runs in the app, with checks on your output.

2The two ways DFS fails

DFS's failures are not edge cases to memorise; both follow directly from expanding newest-first, and both decide real system designs.

Failure one: it may never come back. On an infinite state space — and generated spaces are routinely infinite, since 'append one more token' or 'place one more piece' always offers a next move — DFS can dive down one endless branch while a goal sits two moves from the start on another. On a finite map with cycles, the plain tree-search variant recirculates the loop forever instead. DFS is incomplete without a guard.

Failure two: the answer may be poor. Even when it terminates, the first goal found is whatever the dive hit first, not the nearest — DFS is not optimal under any cost model.

The standard BFS remedy is the wrong medicine here. A full explored set does make DFS terminate on finite graphs, but storing every visited state erases the O(b \cdot m) memory profile that justified DFS in the first place. The lightweight guard is to check for repeats along the current path only — that kills cycles for a memory cost of the path length, and leaves the deeper repair to depth limits.

3Backtracking: DFS as a solver

Backtracking search is DFS wearing work clothes: the states are partial solutions, a move fills in one more piece, and a dead end is a partial solution that already violates a constraint.

Sudoku, n-queens, timetabling, SAT — the industrial constraint solvers all run this shape at their core. DFS's memory profile is exactly right here, because the current path is the current partial assignment, and retreating one level is simply undoing the last choice.

The move that turns it from brute force into an algorithm is pruning: test the constraints the moment a piece is placed, and the search never explores any completion of a doomed prefix — the earlier the cut, the larger the exponential subtree that dies with it.

This is also the first place search and learning meet as colleagues rather than rivals: modern SAT solvers learn which branch to try first from the run so far, but the correctness of the final answer still comes from the exhaustive backtracking skeleton.

Figure. The assignment x = 1 violates a constraint the moment it is placed, so its whole subtree (dashed) is never generated; the search retreats and completes the solution under x = 2. Checking at placement, not at the end, is what lets one comparison discard every completion of the doomed prefix.

The solver cycle

1. AssignExtend the partial solution by one choice — one queen placed, one cell filled.
2. CheckTest the constraints touching that choice immediately, not after the grid is full.
3. UndoOn a violation, retract the choice and try its next alternative; retreat further only when the alternatives run out.

4Depth-limited search

Depth-limited search is DFS with a contract: dive at most \ell moves deep, treat depth-\ell nodes as if they had no children, and report honestly.

Honesty needs three answers, not two. 'Found' and 'no solution anywhere' are the usual pair; the third is 'cutoff' — the limit was hit somewhere, so a solution deeper than \ell may still exist. Collapsing cutoff into failure is a real API bug: it turns 'I did not look further' into 'there is nothing there'.

Choose \ell from problem knowledge when you have it: if every solvable instance is solvable within some known diameter, that diameter is a safe limit. With \ell at or above the goal depth the search is complete; below it, it cannot succeed at all — and it is never optimal, since inside the limit it is still plain DFS.

Alone, depth-limited search looks like a compromise nobody asked for — and alone, it is. Its real role is to be the inner loop that iterative deepening calls with \ell = 0, 1, 2, \dots

5Iterative deepening: BFS answers at DFS prices

Iterative deepening runs depth-limited search with \ell = 0, then 1, then 2, and stops at the first limit that finds a goal. Each individual run is DFS-shaped, so memory stays O(b \cdot d); the limits sweep shallowest-first, so the first solution found is a shallowest one — completeness and unit-cost optimality, the whole BFS contract, at corridor memory.

The objection everyone raises — it re-explores everything, every iteration — dissolves under arithmetic. The level at depth k is regenerated once per iteration from k onwards, so shallow levels are redone many times; but shallow levels are geometrically tiny, and the deepest level, which dominates the total, is generated exactly once.

At branching factor 10 and goal depth 5, all the repetition together costs about 11% extra generation over a single BFS — the worked ledger below has the exact count. That price buys BFS's guarantees with roughly fifty held nodes instead of a hundred thousand.

This is why iterative deepening is the default recommendation for uninformed search when the goal depth is unknown and the space is large. Game engines run the same idea against a clock: deepen until time runs out, and the deepest completed iteration is always a valid answer.

Figure. All of iterative deepening's re-exploration, summed over its six iterations at branching factor 10 and depth 5, is the sliver between the bars: about 11% extra generation. What the figure cannot show is the memory column — about 50 held nodes against 100,000 — which is the entire point of paying the sliver.

Coding lab. Implement iterative deepening runs in the app, with checks on your output.

6Where the DFS family runs in production

The DFS shape may be the most-executed algorithm skeleton in computing, because 'process this thing, then recurse into what it points to' is depth-first search.

Compilers and build tools run it as topological sort — visit a module's dependencies before the module — and the same traversal detects the circular import. Filesystem walks are DFS with directories as nodes. Game engines run their minimax lookahead depth-first to a limit, because the tree is far too wide for one breadth level to fit in memory. SAT and constraint solvers are backtracking, as the solver concept showed.

The selection rule an engineer actually uses: BFS when the answer is about distance from the start; DFS when the whole subtree must finish before its parent, or when memory rules out a level-wide wave; iterative deepening when you want shortest-answer guarantees on a bottomless space or against a clock.