Coding Prep
Recursion
A function that calls itself on a smaller input - the call stack handles bookkeeping so you only need to define the base case and the recursive step, trusting that smaller subproblems are already solved.
What is recursion?
A recursive function solves a problem by calling itself on a strictly smaller version of the same problem. The call stack handles bookkeeping - each call gets its own stack frame with its own local variables. The function never needs to know about the outer calls; it only needs to solve its own smaller piece.
Every recursive function must have two parts: a base case - the smallest input where the answer is known directly, requiring no further call - and a recursive case - a reduction to a smaller version of the same problem followed by a call. Without a base case, the recursion runs forever and the call stack overflows.
The mental model for writing recursive functions: assume the function already works correctly for all strictly smaller inputs (the "leap of faith"). Given that assumption, write only the answer for the current input. This is the recursive step - you don't trace the whole chain; you trust it.
The space cost of recursion is the call stack depth. Linear recursion (one call per level) costs O(n) stack space. Divide-and-conquer recursion (halving the input) costs only O(log n) stack space because only O(log n) frames are active simultaneously, even though the total work may be much more.
Core operations
| Shape | Branches per call | Stack depth | Typical use |
|---|---|---|---|
| Linear recursion | 1 | O(n) | Factorial, reverse linked list, walk a list |
| Binary recursion | 2 | O(log n) to O(n) | Binary search, merge sort, tree traversal |
| Tree recursion | 2+ | O(height) | DFS on trees/graphs, backtracking |
| Mutual recursion | 2 functions | O(n) | Even/odd checks, state machines |
Key patterns
Linear recursion (reduce by one)
Each call does O(1) work then delegates to a problem one step smaller. The return value bubbles back up through the call chain once the base case is reached.
When to use - the problem has a single path of reduction: factorial, summing a list, reversing a linked list, walking a structure one element at a time. There is one smaller subproblem at each step, not a branch into several.
How it works - the base case is the smallest input you can answer directly, with no further call. The recursive case does a little work, then calls itself on an input that is one step smaller, trusting that call to return the right answer. Because each level makes exactly one call, the chain is n frames deep before the base case is hit, so stack depth is O(n). The answer assembles on the way back up as each frame returns to its caller.
Binary recursion (divide and conquer)
Split the problem into two halves, solve each independently, then combine the two results into the answer.
When to use - the problem breaks cleanly into two independent halves that combine easily: merge sort splits then merges, binary search splits and throws one half away, balanced-tree traversal recurses left and right. Reach for it when halving the input collapses the work, turning a linear or quadratic scan into a logarithmic-depth one.
How it works - the base case is a piece small enough to answer directly, usually one element or none. The recursive case cuts the input in half, recurses on each half, then merges the two returned results. When the split is even, the input halves at every level, so the recursion is only O(log n) levels deep and at most O(log n) frames are active at once - the stack stays shallow even when the total work across all calls is much larger. The shallow depth is the whole point: even splits keep the stack at O(log n), unlike a branch that recomputes overlapping subproblems and grows much deeper.
Accumulator pattern (tail-recursive style)
Pass an accumulator argument that carries the result so far. Build the answer on the way down (push down) instead of assembling it on the return path (pop up). This avoids holding many intermediate partial results on the stack at once.
When to use - the problem reads naturally as "carry a running total forward": summing, building a list, folding a value step by step. Reach for it when the plain version stacks up work to finish on the way back up, and you would rather each frame hand the finished-so-far result straight to the next call.
How it works - add a parameter that holds the result accumulated so far, seeded with its identity value (0 for a sum, an empty list for a build). The base case returns the accumulator directly - it already holds the full answer. The recursive case folds the current element into the accumulator and passes it down to the next call, so nothing is left to do on the return path. The chain is still n frames deep in Python, which does not optimize tail calls, but the logic is easier to follow because the answer is complete by the time the base case is reached, not assembled as the stack unwinds.
Canonical examples
Fibonacci with memoization
Naive Fibonacci calls itself twice per level, producing O(2^n) time and O(n) stack depth. Adding a cache (memoization) reduces time to O(n) by returning previously computed results instead of recomputing them. This is the first dynamic programming optimization - the exponential blowup comes entirely from recomputing overlapping subproblems.
Flatten a nested list
Recursion handles variable-depth nesting naturally - if an element is a list, recurse into it; if it is a value, collect it. No iterative solution handles arbitrary nesting depth without maintaining an explicit stack, which duplicates what the call stack already does for free.
When to reach for recursion
- The problem has a naturally recursive structure - trees, nested data, hierarchical problems where each subproblem has the same shape as the whole.
- You need to traverse a tree or graph - DFS is recursive by nature; the call stack replaces an explicit stack.
- The problem decomposes by divide and conquer - split in half, solve each, combine (merge sort, binary search).
- You need to generate all combinations or permutations - backtracking is recursive choose/unchoose over a decision tree.
- The problem involves variable-depth nesting (nested lists, file paths, JSON) - recursion matches the structure without a manual stack.
- The base case is obvious and the recursive step is a strict reduction toward it with no ambiguity.
- A loop-based solution requires you to manually manage a stack - that is the call stack in disguise; recursion is the cleaner expression.
Practice problems
- Fibonacci Number - Linear recursion; compare naive vs memoized call counts.
- Climbing Stairs - Two recursive choices per step; classic memoization intro.
- Maximum Depth of Binary Tree - Postorder recursion; compute result from children up.
- Reverse Linked List - Recursive reversal; trust the smaller list is already reversed.
- Pow(x, n) - Divide-and-conquer exponentiation; O(log n) via halving.
- Flatten Nested List Iterator - Variable-depth recursion; mirrors the structure directly.
Challenges that exercise this
Practical multi-level challenges that put this primer to work.
Done reading? Mark it so it sticks in your dashboard.