CodeWithYash

Intermediate · Module 12 · Lesson 1

Recursion fundamentals

Base cases, recursive contracts, and stack frames.

15–25 min readLesson 64 of 123

Lesson 64 of 123

1d streak

Theory lesson · Step-by-step

Understand Recursion fundamentals

Base cases, recursive contracts, and stack frames.

Worked approach

Trace the reasoning step by step

  1. 1Define the recursive contract and smallest base case for Recursion fundamentals.
  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 factorial(4).

  1. 14 × factorial(3)
  2. 23 × factorial(2)
  3. 32 × factorial(1)
  4. 4Base factorial(1)=1.

Calls return 1, 2, 6, then 24.

What must remain true (Loop Invariant)

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

Cost Model

Complexity & Trade-offs

Recursive evaluation
Recurrence-dependent
O(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 Recursion fundamentals example without looking at the trace.
  • Change one input condition and explain whether the Recursion fundamentals 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.