Recursion

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A method that calls itself on a smaller input. Two parts: a base case that returns directly, and a recursive case that moves towards it.

   #1
2. ↯use it when

   Nested or branching data (trees, folders, JSON), self-similar definitions (row n from row n − 1), and "generate all" problems.

   #2
3. { }template

   if (base) return answer; → smaller = solve(smaller input); → return combine(smaller); Then trust the smaller call.

   #3
4. O( )cost

   Time = calls × work per call. Space = deepest chain of calls. Chain → O(n) · halving → O(log n) · two calls on n − 1 → O(2ⁿ).

   #4
5. !trap

   No reachable base case → frames pile up → StackOverflowError. Java has no tail-call optimization, so depth 10⁴–10⁵ is risky.

   #5
6. !trap

   pow(x, n/2) * pow(x, n/2) makes two calls → O(n). Store half once → O(log n). Same sub-problem twice = wasted work.

   #6
7. !trap

   Backtracking with a shared StringBuilder or List: undo the change after the recursive call, or later branches see leftovers.

   #7
8. ✦pro tip

   Repeated sub-problems? Add a memo (int[] filled with −1, or a HashMap) so each state is solved once. That's top-down DP.

   #8
9. ✦pro tip

   Too deep for the stack? Rewrite with a loop, or an explicit ArrayDeque stack that lives on the heap.

   #9

Shaky on a card? Open the chapter or flip its recall cards.