Recursion & Backtracking

Divide-and-conquer splits a problem into two or more subproblems of the same kind on a fraction of the input, solves them independently, and combines their answers. A function that merely calls itself does none of that by default.

Subsets ask one yes/no question per item: n independent binary decisions, so 2^n outcomes. Orderings fill n positions from a shrinking pool: n choices, then n-1, then n-2, down to 1, which multiplies out to n!.

A cell is marked only to keep the path currently being built from reusing it. Once that branch returns, the cell is no longer on the path, so leaving it marked wrongly blocks every other path that needs to pass through it.

Testing only at the leaf still walks every branch to the bottom. Testing on entry deletes a whole subtree in one return: once the running total is over budget, more items can never bring it back down.

Backtracking explores a decision tree using one shared path structure, so when a branch returns, the choice it made must be removed. Skip that and the next sibling branch starts from a polluted path and explores arrangements nobody ever chose.

A base case only names where to stop; termination also requires every recursive call to move strictly closer to it. If the argument never shrinks, or steps past the base case without matching it, the recursion never ends.

Every unfinished call keeps an activation record on the call stack — parameters, locals, return address. A recursion descending n levels holds n frames at once, so it costs O(n) space even when it allocates nothing.

Every call spawns two more calls, so the calls form a branching tree rather than a straight chain. fib(6) expands into 25 invocations, and most of them recompute values the other branch already computed.

A recursion that makes one self-call as its last act and returns that result unchanged has no pending work, so a loop over its changing parameters replaces it exactly. A recursion with work left after the call must store those frames somewhere.

A call is in tail position only when the caller returns its result directly, with nothing pending afterwards. The added one runs after the call returns, so its frame must survive; carrying the count as an argument removes that work.

Merge sort splits at the midpoint, so its recursion bottoms out after about log n levels. Quicksort splits wherever the pivot lands, and a worst split peels off one element per level, leaving n nested frames.

Divide-and-conquer assumes the branches touch disjoint work. Once the same subproblem is reachable through many different splits, plain recursion recomputes it exponentially often — that is the signal to memoize or tabulate instead.

Three occupancy structures replace the scan: one keyed by column, one by row plus column, one by row minus column. Cells sharing a diagonal share one of those derived keys, so a candidate square is cleared with three constant-time lookups.

You get exactly one ordering — the first — and then the search silently dies. Each marker stays set after its first use, so every later branch finds every item taken and returns without emitting anything. No error, just missing output.

The mark is scoped to one path, not to the whole search, so it is cleared on the way out and the same cell is re-entered by exponentially many different partial paths. The cost is about rows times cols starting points, each exploring roughly 3 to the power of the target length.

The path is one shared structure that keeps mutating. Recording it directly stores a reference, not a snapshot, so every recorded solution aliases the same structure and ends up showing its final, fully undone contents.

Every odd-length input. The remaining count steps by two, so from an odd start it runs 5, 3, 1, -1 and never equals zero. A stride of two needs two base cases: one at n == 0 and one at n == 1.

Two calls per invocation multiply the width of the tree at every level, so the node count doubles level by level and reaches about 2^n over n levels. Multiplying once per level is exponential; O(n^2) would need the work to merely add up.

A stack hands back the most recently pushed item, so children pushed left to right are popped right to left and siblings are visited in the opposite order from the recursion. Push the children in reverse index order to restore it.

Not by itself. Tail position is a property of your code; eliminating the caller's frame is a property of the runtime, and many runtimes never do it. Without a guarantee, depth still grows by one per entry.

Every valid placement holds exactly one queen per row, so the search fixes the rows and chooses only a column at each level. Row conflicts become unrepresentable rather than checked, and the space shrinks from choosing n squares anywhere to n per row.

Binary search recurses into one half only and does no combine work, so its recursion is a chain of about log n calls doing constant work each. Two-way recursion is what creates linear work per level.

The n log n shape comes from one specific recurrence: two half-size subproblems plus linear work outside the recursion. Change how many subproblems you keep, how fast they shrink, or how much work each call does, and the total changes.

Counting accumulates an integer and must exhaust the whole tree. Returning one solution returns a success flag that short-circuits every frame above it the moment a full placement is reached. Returning all solutions must snapshot each placement, because the working state keeps being mutated.

Indexing first reads a cell that does not exist. Bounds-checked runtimes raise an error; unchecked ones read whatever memory is adjacent, and a flat row-major grid silently wraps a column overflow into the neighbouring row, producing a wrong answer with no error at all.

Every later branch inherits dirty shared state: the abandoned item is still on the path and its price still in the running total. Affordable bundles get pruned as over budget, and recorded results contain an item never actually chosen.

Position-like values such as the current slot or depth travel as parameters: each call frame holds its own copy, so returning restores the caller's value for free. Anything shared across depths lives in the path and needs an explicit undo.

The base case returns 0 for a childless comment, so no call ever counts the node it was handed. A childless comment is one comment — the base must return 1, matching the contract the recursive branch relies on.

The ceiling is a byte budget, not a call count: a fixed-size stack region divided by the size of each frame. Fatter frames from more parameters or bigger locals overflow sooner, so identical recursion shapes fail at very different depths.