Algorithms from zero
Recursion and backtracking: code reading
Crux Read real recursive snippets and a recursion tree, predict their behaviour or cost, and pick the bug or the highest-leverage fix.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skyRecursion bugs are found by reading code and tracing the calls, not by guessing. Read each snippet, predict what it does, and choose the answer a careful engineer would defend in review.
Goal
Practise the loop you run on any recursive function: find the base case, check that the recursive case makes progress, count the branching to read the cost, and verify backtracking restores its state before the next choice.
Snippet 1 — the missing progress
function sumDigits(n) {
if (n === 0) return 0; // base case
return (n % 10) + sumDigits(n / 10); // recursive case
}
sumDigits(123); Quiz
Completed
This is meant to sum the decimal digits of n. What actually happens, and why?
Heads-up It would if n / 10 were integer division. In JavaScript / is float division, so n never reaches exactly 0 and the base case is never met; the recursion does not terminate.
Heads-up There is no termination at all. Because n never becomes exactly 0, no base case fires and the call stack grows until it overflows.
Heads-up Widening the base case papers over the symptom. The real defect is that the recursive case fails to step toward 0 in integer increments. Use floor division so the argument shrinks to 0.
Snippet 2 — the recursion tree
fib(4)
├─ fib(3)
│ ├─ fib(2)
│ │ ├─ fib(1)
│ │ └─ fib(0)
│ └─ fib(1)
└─ fib(2)
├─ fib(1)
└─ fib(0) Quiz
Completed
Reading this call tree for naive fib(4), which statement is correct?
Heads-up Look again: fib(2) appears twice and fib(1) three times. The naive version has no memory, so overlapping subproblems are recomputed, giving exponential work.
Heads-up The 9 nodes are total calls over time, not simultaneous frames. The stack holds only one root-to-leaf path at a time, so the maximum depth here is about 4.
Heads-up fib(n) calls fib(n-1) and fib(n-2): branching factor 2. The tree is correct; the lesson is the repeated subproblems, not the branch count.
Snippet 3 — the leaked state
function subsets(arr) {
const result = [], current = [];
function go(i) {
if (i === arr.length) { result.push(current); return; }
current.push(arr[i]);
go(i + 1);
current.pop();
go(i + 1);
}
go(0);
return result;
} Quiz
Completed
The choose-explore-undo structure looks right. Why does this return an array of empty (or identical) subsets?
Heads-up The pop is correctly placed between the include and exclude branches; the choose-explore-undo order is fine. The bug is storing a live reference instead of a snapshot copy.
Heads-up Both branches must advance to i + 1 to move through the elements; calling go(i) would not make progress. The defect is the missing copy when recording a complete subset.
Heads-up Subsets branch include/exclude per index and need no used array. The only fault is pushing the shared current by reference instead of copying it.
Snippet 4 — the pruning question
function combine(arr, k) {
const result = [];
function go(start, current) {
if (current.length === k) { result.push([...current]); return; }
for (let i = start; i < arr.length; i++) {
current.push(arr[i]);
go(i + 1, current);
current.pop();
}
}
go(0, []);
return result;
} Quiz
Completed
This generates C(n, k) combinations correctly. What does adding `if (current.length + (arr.length - start) < k) return;` at the top of go change?
Heads-up The base case still only records when current.length === k, so the output is unchanged. The check only skips branches that provably cannot reach size k.
Heads-up The start index already prevents duplicates by walking forward only. The prune cannot add duplicates; it just avoids exploring branches with too few remaining items.
Heads-up If current.length plus all remaining items is still below k, no completion of this branch can ever reach k, so nothing valid is skipped. It is a sound prune.
Recap
Every recursive bug is read the same way: confirm the base case can actually be reached (Snippet 1’s float division never hits 0), watch for overlapping subproblems that make the tree exponential (Snippet 2’s repeated fib calls), copy the partial solution when you record it instead of storing a shared reference (Snippet 3), and add pruning that skips provably dead branches without changing the output (Snippet 4). Trace the calls, fix the progress or the state, then re-check.