DSA & Implementation · intro
Recursion & Induction
Writing recursion you can trust, and solving the recurrence it produces.
Mental model
Trust the recursive call. You verify a base case and verify that the recursive step is correct ASSUMING the call on a smaller input is correct — that is induction, and it is why tracing the whole call tree in your head is both unnecessary and the main source of confusion. Every recursion also implies a recurrence, and the Master theorem reads it off directly: T(n) = aT(n/b) + f(n) is decided by whether the work at the leaves or at the root dominates.
How to study Recursion & Induction
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use the linked roadmap and primary implementation references to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Recursion & Induction with 1D DP, Backtracking, Trees. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Solve a divide-and-conquer recurrence and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Where it matters
Tree and graph traversal, divide-and-conquer, parsers, and every dynamic-programming formulation before it is memoised.
Common mistakes
- Tracing execution instead of trusting the inductive hypothesis, then getting lost three levels deep
- A base case that does not actually terminate every path — off-by-one on the shrink step
- Recursing without shrinking the input, or shrinking it in a way that skips the base case
- Ignoring stack depth: an O(n) recursion on a million elements overflows where a loop would not
Learn from primary sources
Use the linked roadmap context and practice prompt.
Practice and explain it back
Solve a divide-and-conquer recurrence
Implement masterCase(a, b, fExp) for T(n) = a*T(n/b) + n^fExp. Let c = log_b(a). Return 'leaves' when fExp < c (leaf work dominates, T = n^c), 'balanced' when fExp === c (T = n^c log n), 'root' when fExp > c. Compare with a small tolerance — log_b(a) is floating point.
Expected evidence: masterCase(2,2,1) -> 'balanced' (mergesort); masterCase(8,2,2) -> 'leaves'; masterCase(2,2,2) -> 'root'
Open the interactive drill →Review prompts
- You are three levels deep tracing a recursive call and have lost the thread. What is the argument that makes tracing unnecessary, and what must you check instead?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.