CodeWithYash

Intermediate · Module 12 · Lesson 6

Memoized recursion

Cache repeated states before moving to tabulation.

15–25 min readLesson 69 of 123

Lesson 69 of 123

1d streak

Theory lesson · Step-by-step

Understand Memoized recursion

Cache repeated states before moving to tabulation.

Worked approach

Trace the reasoning step by step

  1. 1Define the recursive contract and smallest base case for Memoized recursion.
  2. 2List the choices or independent subproblems available at the current state.
  3. 3Apply one choice, recurse on a strictly smaller state, and combine the result.
  4. 4Undo mutable state before exploring the next sibling branch.
  5. 5Add pruning only when it cannot remove a valid solution.

Concrete example

Compute Fibonacci(6) without repeating states.

  1. 1Cache fib(2)…fib(5) after first computation.
  2. 2Later calls return cached values.

Only O(n) distinct states are solved.

What must remain true (Loop Invariant)

Each call in Memoized recursion owns one well-defined subproblem; on return, its temporary choice is fully undone unless it belongs to the result.

Cost Model

Complexity & Trade-offs

Cached state graph
O(states × transitions)
O(states + depth)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Self-similar subproblems, enumeration, constraint solving, and decision trees.
  • Generating combinations and permutations.
  • Converting overlapping recursion into dynamic programming.

Common mistakes

  • Missing a base case or failing to make strict progress.
  • Forgetting to undo shared mutable state.
  • Using exponential search when states repeat and should be memoized.

Practice prompts

  • Reproduce the worked Memoized recursion example without looking at the trace.
  • Change one input condition and explain whether the Memoized recursion invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.