Depth-first search & iterative deepening

DFS with a LIFO stack / recursion + cycle check; the BFS↔DFS space/optimality trade-off; DFID as the best of both.

Go deep first

Depth-first search (DFS) drives down a single path as far as it can before considering any alternative. Where BFS used a FIFO queue, DFS uses a LIFO stack for OPEN: new children are pushed onto the front and the next state is taken from the front — so the most recently discovered state is expanded next, plunging the search deeper. The only structural change from BFS is queue → stack; everything else (OPEN/CLOSED, child generation, cycle detection) is identical.

Equivalently — and this is how the exam expects you to write it — DFS is natural recursion: visit a node, then recurse into each child in turn. The language's own call stack is the OPEN stack, and the chain of activation records is the current path. Backtracking happens automatically: when every child of a node fails, the recursive call returns FAIL and control returns to the parent, which tries its next child.

The trade-off against BFS

	BFS	DFS
OPEN	FIFO queue	LIFO stack (or recursion)
Space	$O (B^{n})$ — whole frontier	$O (B \cdot n)$ — one path
Shortest path?	yes (fewest arcs)	no
Risk	runs out of memory	can loop forever without a visited set; can dive down an infinite branch

DFS's linear space is its great virtue: for $B = 10$ , depth 10, DFS holds about $10 \times 10 = 100$ states versus BFS's $1 0^{10}$ . But DFS gives up the shortest-path guarantee, and without a visited/cycle check it can loop forever on a cyclic graph.

Depth-first iterative deepening (DFID)

DFID gets both good properties. Run a depth-limited DFS with limit 1, then 2, then 3, … restarting from scratch each round and discarding state between rounds. Because the goal is found at the smallest depth that contains it, DFID inherits BFS's shortest-path guarantee; because each round is a plain DFS, it keeps DFS's linear space $O (B \cdot n)$ . It looks wasteful — shallow levels are regenerated every round — but since the number of nodes grows exponentially with depth, the deepest level dominates the total work and the re-generation cost is negligible (Korf, 1987). DFID is the preferred uninformed search when you need both shortest paths and bounded memory.

Worked example — same graph, contrast the order

Reuse the graph from the BFS lesson:

A → B, C    B → D, E    C → F    D → F

From A to F, DFS dives into the first child each time: A → B (first child) → D (B's first child) → F. It returns the path A → B → D → F — three arcs, longer than the two-arc A → C → F that BFS found, because DFS commits to the first branch rather than sweeping levels. Running depth-limited DFS with growing bounds, DFID first fails at depth 0 and 1 (the goal sits below) and succeeds at depth 2 — the shallowest depth at which F is reachable, recovering the optimal answer. The runnable cell prints both results.

Compare this against the breadth-first figure in the previous lesson — same graph, same start, same goal, different OPEN list. DFS takes the first child every time, so it commits to B and returns a three-arc path; it never even looks at C, the node that carried the two-arc answer.

DFID is the only column with a tick in both the space row and the fewest-arcs row, which is the whole reason it exists. It pays for that by re-generating the shallow levels every round — cheap, because the deepest level holds most of the nodes.