Recursion & Backtracking

One extra ply multiplies the whole search by about three: each position at the current frontier fans out into three more. Depth-limited search cost is dominated by the deepest level, so deepening is a multiplication, never an increment.

Pushing children captures only the descent. A real frame also remembers where to resume, because the parent still owes work once its children finish. Push each node twice with a phase tag so the parent is revisited after its subtree completes.

Eliminating a tail call discards the caller's activation record, and those records are what stack traces, debuggers, profilers and caller-chain security checks read. Runtimes that prize diagnosability refuse the trade deliberately, not by oversight.

Ordered input makes every split lopsided, so the recursion holds one frame per record. Recurse into the smaller partition and loop on the larger — the smaller side is at most half, capping depth at log n.

The combine step must check pairs that straddle the dividing line, since the closest pair overall may have one point on each side. It stays cheap by using the recursion's own distance to bound the search to a narrow band.

Sorting makes equal items adjacent so the check can be local. The guard then fixes one canonical order among identical items: a twin may only be placed once its left neighbour already is. Reverse the test and the second twin can never be placed at all.

A membership test only rules a branch out at full target length, by which point the whole subtree has already been explored. A prefix test rules it out at depth d and discards everything beneath — and the subtree beneath is where all the cost lives.

Copy when the state is small or the recursion shallow, buying safety with the constant factor. Copying costs the state's size at every node and one live copy per level; mutate-and-undo costs little but demands a restore on every exit.

Stop materialising the output. Every arrangement here is valid, so nothing can be cut from the search; the memory goes on the returned collection. Hand each solution to a consumer at the leaf, or fold it into a count or aggregate.

Because the termination argument silently assumes integer division rounds toward zero. Under rounding toward negative infinity the value sticks at -1 and never equals 0. Negating the input first is not a safe fix: the most-negative fixed-width value has no positive counterpart.

Recursion depth tracked input size, so thousand-record fixtures held a thousand frames while the production chain demanded a thousand times more than the stack region could hold. Stack exhaustion has no warning curve: it works, then it aborts.

Label every node with the arguments the invocation received — the position and the remaining depth — instead of with the move that led there. Repeated labels are repeated work: identical labels have identical subtrees beneath them.

First establish whether the depth was legitimate. If real data is genuinely that deep, an explicit stack moves the frames into memory that grows on demand and fixes it. If a cycle or bad parent link caused it, conversion only turns a fast crash into an out-of-memory.

A specified guarantee from the target, plus its scope: self-recursion only or general tail calls, which build modes it covers, whether the call still qualifies inside exception handlers. A large passing test is an observation, not a guarantee.

When measured headroom, not asymptotics, says so. A quadratic scan over a few thousand points is a few million tight comparisons and often fits the budget; the decision turns on projected growth, tail latency today, and maintenance risk.

No. Thirty flags means over a billion configurations, and no pruning trick rescues an exponent you have no constraints to prune with. The work becomes scoping: enumerate only within interacting groups, encode real constraints, cover the rest pairwise, and cap flag growth.

Pruning improves the average case, never the exponential worst case, so measurements on today's traffic cannot promise a latency bound. Ship only behind a bounded input size, a hard node budget with a defined fallback answer, and alerting on cap-hits.

Decide by what removes the failure class versus what the team can maintain. Reshaping the data bounds depth permanently but touches producers; an explicit stack keeps the algorithm and relocates linear state; caps buy time with a documented rejection.

Both emit the same rosters. Include-exclude asks one in-or-out question per engineer, giving a binary tree of depth n. The index-loop picks the next member from those after the last chosen, giving a tree of depth k with wide fan-out.

Plain checking looks backward, confirming the new assignment conflicts with nothing already chosen. Forward checking looks ahead: it deletes the newly illegal values from the domains of variables not yet assigned, and backtracks the moment any of those domains becomes empty.