Recursive Thinking & Backtracking

Pseudocode & Algorithmic Problem-Solving

Chapter 9 · Recursive Thinking & Backtracking

Chapter 8's divide-and-conquer algorithms were already recursive — this chapter names that pattern explicitly, then builds on it with backtracking: a systematic search that abandons a partial candidate the moment it's known to be hopeless, rather than generating and checking every full candidate the way Chapter 6's brute force did.

Recursion, Formalized: Base Case + Recursive Case

Every recursive algorithm needs exactly two things: a base case simple enough to answer directly, and a recursive case that calls the same algorithm on a smaller version of the problem, then uses that result to build the current answer.

ALGORITHM Factorial(n)
    IF n = 0 THEN
        RETURN 1                      // base case
    ENDIF
    RETURN n × Factorial(n - 1)          // recursive case
    

Verified directly — the full call chain, and a match against a trusted reference

Factorial(5) calls Factorial(4), which calls Factorial(3), down to Factorial(0) — the base case, returning 1 — and each level then multiplies that result back up: 1×1=1 → 2×1=2 → 3×2=6 → 4×6=24 → 5×24=120. The result, 120, matches Python's own built-in math.factorial(5) exactly.

Backtracking: A Prune-as-You-Go Alternative to Brute Force

Chapter 6 verified that checking all 2ⁿ subsets of a set explodes fast — over a trillion for just 40 items. Backtracking attacks the exact same kind of problem differently: build a candidate one item at a time, and the moment a partial candidate is provably unable to lead anywhere valid, stop extending it immediately — never even generate the full candidates that would have grown from it.

ALGORITHM SubsetSumBacktrack(items, index, current_sum, target)
    IF current_sum = target THEN
        RETURN SUCCESS                              // found it
    ENDIF
    IF current_sum > target THEN
        RETURN FAILURE                              // PRUNE: can't recover from here
    ENDIF
    IF index = length(items) THEN
        RETURN FAILURE                              // out of items, no match
    ENDIF
    // try including items[index]...
    IF SubsetSumBacktrack(items, index+1, current_sum + items[index], target) = SUCCESS THEN
        RETURN SUCCESS
    ENDIF
    // ...or try excluding it
    RETURN SubsetSumBacktrack(items, index+1, current_sum, target)
    

Verified directly — the exact Chapter 6 problem shape, solved with a fraction of the work

Searching [15, 22, 8, 31, 17, 9, 25, 12, 19, 6] for a subset summing to 35: Chapter 6's brute force would check all 2¹⁰ = 1,024 candidate subsets. This backtracking version finds the correct answer — [15, 8, 12], which sums to exactly 35 — after exploring only 22 nodes: roughly 46 times fewer than the full brute-force enumeration, for the identical problem and the identical correct answer.

Why the pruning rule is honest, not a trick

The prune condition — stop as soon as current_sum > target — is only valid because every item in this problem is positive: once the running sum overshoots the target, adding any more (positive) items can only make it worse, never bring it back down. This is exactly the same discipline Chapter 7 demanded of greedy algorithms: a shortcut is only safe when it's backed by a real, checkable fact about the problem — here, that every remaining choice can only move the sum in one direction. Backtracking on a problem containing negative values would need a different (or no) pruning rule.

Backtracking vs. Brute Force, Side by Side

	Brute Force (Ch.6)	Backtracking (this chapter)
Builds candidates	All at once, fully formed	Incrementally, one item at a time
Rejects a bad candidate	Only after it's fully built and checked	The moment it's provably hopeless — before it's ever finished
Verified cost for this problem	`1,024` candidates checked	`22` nodes explored
Requires	Nothing extra — works on any well-defined candidate set	A provable, problem-specific pruning rule

Where This Connects

This chapter's finding	What it resolves or sets up
Backtracking exploring 22 nodes vs. brute force's 1,024	A direct, measured resolution of Chapter 6's own explosive subset-sum warning — the same problem shape, made tractable by a valid pruning rule
A pruning rule justified by a real property of the problem (all-positive items)	Echoes Chapter 7's own honest standard for trusting a shortcut — never assumed, always checked
Base case + recursive case, formalized	The exact structure Chapter 10's capstone uses to actually implement whichever design strategy it settles on

Hands-On Exercises

Exercise 1

Using this chapter's own Factorial pseudocode, hand-trace the full call chain for Factorial(4), showing every recursive call down to the base case and every multiplication as the results combine back up.

📄 View solution

Exercise 2

Using this chapter's own SubsetSumBacktrack pruning rule, explain what would go wrong if the item list [15, 22, 8, 31, 17, 9, 25, 12, 19, 6] were changed to include a negative number (for example, -5), and why the algorithm's current pruning condition (current_sum > target) could then cause it to miss a valid answer.

📄 View solution

Exercise 3

Using this chapter's own side-by-side comparison table, explain in your own words why backtracking's 22-node search and brute force's 1,024-candidate search both count as "checking every possibility" in some sense, yet only one of them is described as exhaustive in the way Chapter 6 used that word.

📄 View solution

Chapter 9 Quick Reference

Recursion: a base case (answered directly) + a recursive case (calls itself on a smaller input) — verified with a full Factorial(5) call chain matching Python's own math.factorial(5)
Backtracking: build a candidate incrementally, abandon it the instant it's provably hopeless — never finish generating candidates that can't possibly work
Verified directly: backtracking solved the exact subset-sum problem Chapter 6 flagged as explosive using only 22 explored nodes, versus brute force's full 1,024-candidate enumeration — the identical correct answer, ≈46× less work
A pruning rule is only valid when backed by a real, checkable property of the problem (here: all items positive) — the same honesty standard Chapter 7 demanded of greedy shortcuts
Next chapter: Capstone — designing a full algorithm from a real-world problem statement, using every strategy this course has built