Recursion Fundamentals¶
Also known as: Recursive Thinking, Base Case and Recursive Case, Divide and Conquer (Basics)
Solve a problem by assuming you can already solve a smaller version of it, then defining how to combine that smaller answer into the full one. The whole skill is trusting the recursive call instead of trying to trace every level in your head.
Before you start¶
- Comfortable with writing functions and understanding how function calls return values in your language.
What 'solved properly' looks like
Target: Varies per problem — the depth is the key concern, not the time complexity alone. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You write a function that calls itself on a smaller input. Every recursive function has two parts: the base case (the smallest version of the problem that you return directly) and the recursive case (where you combine the result of the smaller call with some extra work). The recursion stack handles the bookkeeping of where you are — you just define the base and the combination rule.
Why it matters: Trees, graphs, backtracking, and dynamic programming are all recursion wearing different clothes. This is the stage where it either clicks or haunts you for the rest of the roadmap. Getting comfortable with the "leap of faith" — assuming the recursive call works correctly — is the single most important skill to develop here.
When to reach for it¶
Reach for it when a problem is naturally defined in terms of itself: computing f(n) from f(n-1), traversing a tree where each node has children that are also trees, exploring choices where each choice leads to more choices, or any nested structure.
When not to use it
No base case (or an unreachable one) means a stack overflow, not a wrong answer. Recomputing the same subproblem over and over is what makes naive recursion exponential — that's the exact wound dynamic programming later heals, so notice it happening here. And deep recursion can exhaust the call stack on large inputs; sometimes the iterative version isn't optional.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Fibonacci Number | LeetCode | Easy | 15 mins | teaching |
| 2 | Power of Two | LeetCode | Easy | 15 mins | teaching |
| 3 | Merge Two Sorted Lists | LeetCode | Easy | 20 mins | consolidation |
| 4 | Pow(x, n) | LeetCode | Medium | 25 mins | consolidation |
| 5 | Binary Tree Inorder Traversal | LeetCode | Easy | 20 mins | challenge |
Already know this? Test out.
If you can solve Binary Tree Inorder Traversal cleanly in one sitting — writing the recursive traversal from memory — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.