Algorithms from zero
Recursion and backtracking: multiple-choice review
Crux Multiple-choice synthesis across the recursion unit: base/recursive case, call stack depth, recursion-tree complexity, the backtracking template, and pruning.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skySix questions that cut across the whole unit. Each one is a decision you make when you actually write recursive code, not a definition to recite, but a judgement about correctness, cost, or which fix is right.
Goal
Confirm you can connect the four ideas the unit built: a base case and a shrinking recursive case make recursion terminate, the call stack sets space, the recursion tree sets time, and backtracking with pruning turns brute force into something practical.
Quiz
Completed
A recursive function has a base case but still overflows the stack on every input, including tiny ones. What is the most likely cause?
Heads-up A wrong base-case return gives a wrong answer, not a stack overflow. Overflow means the recursion never stops, which is a progress problem in the recursive case.
Heads-up Recursion does not need a loop. The defect is that each call must move closer to the base case; if the argument does not shrink, the base case is unreachable.
Heads-up If it overflows even on tiny inputs, the recursion is not making progress. A correct shrinking recursion on small n would never overflow.
Quiz
Completed
factorial(n) and naive fibonacci(n) both recurse to depth n. Why is factorial fine for large n while fibonacci is not?
Heads-up Stack depth is set by the deepest path, not the total number of calls. Both reach depth n, so both use O(n) stack. The difference is total work, the number of nodes in the recursion tree.
Heads-up Both have base cases and both terminate. Fibonacci is slow because its branching factor of 2 makes the recursion tree exponential, not because it fails to stop.
Heads-up They recurse to the same depth n. The branching factor (2 vs 1), not the depth, is what makes fibonacci's node count explode to O(2^n).
Quiz
Completed
A recursive function has branching factor b = 3 and depth d = 12, doing O(1) work per call. Roughly how many calls does it make, and what does that tell you?
Heads-up Branching factor and depth multiply per level, not once. Each level multiplies the node count by b, giving b^d, not b times d.
Heads-up The base is the branching factor and the exponent is the depth: b^d = 3^12, not d^b. Swapping them drastically undercounts.
Heads-up That is the stack depth, not the call count. With branching, each level has up to b times as many nodes as the one above it.
Quiz
Completed
In the choose-explore-undo backtracking template, what breaks if you omit the undo step (push to current but never pop)?
Heads-up Termination is controlled by the base case, not the undo. Without undo the recursion still stops, it just produces wrong partial solutions along the way.
Heads-up Undo is required for correctness with shared mutable state. The shared current array must be clean before the next sibling choice, or every later branch inherits leftover elements.
Heads-up Pruning is the is-valid check before recursing; it is independent of undo. Skipping undo corrupts the partial solution, which is a separate defect.
Quiz
Completed
Subsets, permutations, and combinations all use the same backtracking template. What actually distinguishes them?
Heads-up All three are written with the same recursive backtracking skeleton in this unit. What changes is the choice logic and the base case, not recursion vs iteration.
Heads-up Combinations have a natural prune (not enough items left to reach k), but pruning is a general backtracking idea. The defining difference is the choice rule, not who can prune.
Heads-up They have different output sizes: 2^n subsets versus n! permutations. They differ because order matters for permutations but not for subsets.
Quiz
Completed
A correct recursive tree-walk works in tests, but a colleague says it must be rewritten iteratively before production. When is that warranted?
Heads-up Recursion and iteration usually share the same time complexity. The concern is stack space at large depth, not raw speed; shallow recursion needs no rewrite.
Heads-up Correct on small inputs can still overflow the stack on large depth. If depth scales with input, an explicit-stack iterative version removes that hard limit.
Heads-up A missing base case is a bug to fix outright, not a recursion-vs-iteration tradeoff. The real iterative-rewrite trigger is unbounded stack depth.
Recap
The unit’s through-line is one chain: a base case plus a shrinking recursive case make recursion terminate; the call stack makes depth cost O(depth) in space; the recursion tree makes total work the branching factor raised to the depth in time; and backtracking applies that recursive skeleton (choose, explore, undo) with pruning to skip doomed branches. Get the base case and progress right first, then read time from the tree and space from the stack.