Recursion, Backtracking, And Memoization

Recursion solves a problem through smaller instances. Backtracking explores choices and undoes them. Memoization caches repeated subproblem results.

Why This Matters

These techniques can express trees and combinatorial search clearly, but deep stacks and explosive search spaces require limits and pruning.

Working Model

A recursive function needs a base case and progress toward it. Backtracking maintains partial state, tries a choice, explores, then restores state. Memoization keys results by every input that affects the answer.

Practical Rules

  • Define the base case first.
  • Limit depth and total work.
  • Avoid shared mutable recursion state.
  • Memoize only deterministic subproblems.
  • Prefer iteration when depth may be large.

Failure Modes

  • Missing progress toward a base case.
  • Caching by an incomplete key.
  • Using recursion for untrusted deeply nested data.
  • Generating every combination when constraints can prune early.

Verification

  • Test base and boundary cases.
  • Count explored states.
  • Compare memoized and non-memoized outputs.
  • Test depth limits and cycles.

What You Should Be Able To Do

After this lesson, you should be able to explain recursive decomposition, backtracking state, memoization keys, and safe limits, choose a suitable approach for a real PHP project, and verify the result instead of relying on assumptions.

Practice

Practice: Memoize Path Counts

Count routes through a grid with blocked cells.

Your answer must:

  • state the intended outcome;
  • show the commands, data flow, or implementation shape;
  • identify at least one unsafe alternative;
  • explain how the result will be verified.
Show solution

Cache results by row and column, return zero for blocked or out-of-range cells, and return one at the destination. Verify against a small hand-counted grid.

The important part is not memorising one command or vendor screen. The solution makes the invariant, failure behavior, and verification evidence explicit.

Practice: Backtrack A Schedule

Assign a small set of jobs to valid time slots.

Your answer must:

  • state the intended outcome;
  • show the commands, data flow, or implementation shape;
  • identify at least one unsafe alternative;
  • explain how the result will be verified.
Show solution

Choose the next constrained job, try each permitted free slot, recurse, and undo the assignment on failure. Prune as soon as a constraint fails.

The important part is not memorising one command or vendor screen. The solution makes the invariant, failure behavior, and verification evidence explicit.

Practice: Replace Deep Recursion

Traverse deeply nested imported data without risking stack exhaustion.

Your answer must:

  • state the intended outcome;
  • show the commands, data flow, or implementation shape;
  • identify at least one unsafe alternative;
  • explain how the result will be verified.
Show solution

Use an explicit stack containing nodes and depth, enforce a maximum depth and node count, and track identities if cycles are possible.

The important part is not memorising one command or vendor screen. The solution makes the invariant, failure behavior, and verification evidence explicit.