Recursive Depth-First Backtracking¶
Method — instantiates Constraint-Guided Backtracking
A recursive method that extends a partial state one commitment at a time and returns to the prior choice point when a branch cannot complete.
Recursive Depth-First Backtracking is the archetype's canonical engine: a procedure that calls itself to extend a partial solution by one commitment, plunges as deep as it can down a single branch, and — the moment a branch is proven unable to complete — simply returns from the recursive call, which discards the most recent commitment and lands the search back at the previous choice point to try the next candidate. Its defining trait is that the machinery is the recursion: the language's call stack behaves as the decision stack, "return" behaves as the rollback, and the entire search is one function walking a tree by going down before it ever goes across. Nothing about state fidelity, look-ahead, or human judgment lives here — this mechanism is pure traversal control.
Example¶
A Sudoku solver fills the grid one empty cell at a time. It picks the first blank cell and tries the digit 1; if that is legal against the row, column, and box, it recurses into the next blank cell and tries again from 1. Suppose it reaches a cell where no digit 1–9 is legal — every candidate collides with an existing entry. That call has nothing left to try, so it returns. Control unwinds to the cell where the last guess was placed, which advances to its next untried digit and recurses afresh.
Trace a fragment: cell A commits 3, recurse; cell B commits 7, recurse; cell C finds no legal digit → return to B; B advances to 8, recurse; and so on. The solver never wipes the grid and starts over; each dead end costs exactly one level of unwinding and the valid prefix above it survives untouched. The recursion bottoms out in only two ways — the grid fills completely (a solution) or the very first cell exhausts all nine digits (a proof that none exists). That is the whole method: extend, recurse, fail, return.
How it works¶
- Extend. At the current partial state, propose the next commitment (choose a slot and a candidate value) and apply it.
- Recurse. Descend into the extended state and repeat, going as deep as the branch allows.
- Fail and return. When the current state admits no legal extension, the call returns — automatically undoing its own commitment and handing control back to the caller, which tries its next candidate.
- Terminate. Stop at the base cases: a complete valid state (success) or the root running out of candidates (exhaustion).
The rollback is always chronological — you retreat to the most recent open choice, never further — because "return" can only pop the frame you are in.
Tuning parameters¶
- Value ordering — which candidate a cell tries first. A good order finds solutions faster but never changes completeness; a bad one only wastes descents.
- Variable/slot selection — which undecided part to extend next. Choosing the most-constrained slot first tends to fail fast and shrink the tree.
- Constraint-check eagerness — test after every single extension, or only at intervals. Eager checking catches conflicts sooner at more cost per step.
- Recursion/stack depth — the maximum depth the call stack may reach before the method must switch to an iterative or bounded variant. Deep problems can overflow a naive recursion.
- Memoization — caching results of equivalent sub-states to avoid re-exploring them, trading memory for speed.
When it helps, and when it misleads¶
Its strength is completeness at a tiny footprint: with correct base cases it will find a solution if one exists or prove none does, using only the space of the current path. It preserves the valid prefix for free — a failure discards exactly one commitment, not the work above it.
Its central failure mode is thrashing: plain chronological backtracking rediscovers the same conflict at many different leaves, because it always retreats to the latest choice even when a much earlier choice is the real culprit — the pathology that conflict-directed backjumping and no-good learning were invented to cure.[n1] Worst-case cost is exponential, and a hard problem with a bad branch order can crawl. The guarding discipline is to pair the raw method with look-ahead pruning and a smart branch order, and to reach for backjumping when a single deep conflict is poisoning many branches — rather than trusting depth-first return alone on a large search.
How it implements the components¶
Recursive Depth-First Backtracking fills the traversal-control core of the archetype — the parts that decide where the search goes and when it retreats:
extension_operator— each recursive call applies exactly one legal next commitment to the current partial state.decision_stack— the language call stack is the ordered ledger of commitments; the innermost frame is always the newest reversible one.rollback_rule— "return from the call" is chronological rollback: retreat to the most recent open choice and try its next candidate.completion_or_exhaustion_condition— the two base cases that end the recursion: a complete valid state, or a root with no candidates left.
It does not guarantee that a restored state is coherently reconstructed beyond the call frame — preserved_context_boundary and rollback_depth_limit are Undo-Stack Protocol, the nearest twin; where this method decides when and where to retreat, that protocol guarantees the retreat lands on an intact state. It also does not look ahead to prune doomed branches (forward_checking_probe) — that is Forward-Checking Table.
Related¶
- Instantiates: Constraint-Guided Backtracking — this method is the reversible-search engine the archetype describes in the abstract.
- Consumes: Forward-Checking Table — an optional look-ahead the recursion can call after each extension to abandon doomed branches before descending.
- Sibling mechanisms: Undo-Stack Protocol · Forward-Checking Table · Chronological Backtracking Log · Decision-Tree Search Diagram · Hypothesis-Tree Review · Constraint-Satisfaction Solver Pass
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Recursive Depth-First Backtracking operates as an analytical, modeling, inference, comparison, or optimization procedure that derives insight or a solution because it a recursive method that extends a partial state one commitment at a time and returns to the prior choice point when a branch cannot complete.
Independent corroboration: The frozen evidence defines Recursive Depth-First Backtracking as 'A recursive method that extends a partial state one commitment at a time and returns to the prior choice point when a branch cannot complete', so its operative form is Analysis, Modeling & Optimization.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Recursive depth-first search with backtracking is a canonical computer-science algorithm.
Review resolution: Both blind reviewers agree that computer_science is the primary origin. Explicit reconciliation of alternate origin disagreement, origin mode disagreement adopts reviewer_a's classification because recursive depth-first search with backtracking is a canonical computer-science algorithm. The resulting lineage records alternates=none, origin_mode=single_lineage, and domain_reach=specialized; these describe formative provenance separately from later applicability.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] Conflict-directed backjumping retreats not to the most recent choice but to the earliest choice implicated in the conflict, and no-good learning records the offending combination so it is never retried. Both are standard corrections for the thrashing that pure chronological (return-based) backtracking suffers when a deep conflict has a shallow cause. ↩