Recursion: Complete Guide to Base Cases and Memoization
Recursion is a function that calls itself to solve a smaller copy of the same problem. It is the natural tool for walking trees and graphs, exploring combinations, and processing nested data. Most of the other patterns on this site sit on top of recursion at some level. Tree traversal, backtracking, and divide and conquer all call functions on smaller inputs and combine the results. An interviewer who asks for any of those will expect you to reason about the recursion underneath.
Definition: a recursive function has two parts. The base case is the smallest input that returns an answer directly, with no further calls. The recursive case reduces the input and calls the function again. When the recursive case finally reaches the base case, every pending call unwinds and returns its answer to the caller.
Real-World Analogy
Picture a nesting doll with many layers. To count the layers, you open the outer doll, take out the next doll, and then you are doing the exact same task on a smaller object. You keep opening until the innermost doll contains nothing inside. That innermost doll is the base case. Every doll above it does one small piece of work, then reports the total back to the doll that opened it.
A recursive function behaves the same way. Each call handles a smaller input, waits for the result, and adds its own contribution before returning. Nobody ever has to think about the whole problem at once. Each level only needs to understand its own small step.
Visual Explanation
The classic example is the Fibonacci sequence, where each number is the sum of the two previous numbers. Here is what the calls look like when you compute fib(4) without caching.
graph TD
F4["fib(4)"] --> F3["fib(3)"]
F4 --> F2["fib(2)"]
F3 --> F2b["fib(2)"]
F3 --> F1a["fib(1)"]
F2 --> F1b["fib(1)"]
F2 --> F0a["fib(0)"]
F2b --> F1c["fib(1)"]
F2b --> F0b["fib(0)"]
Notice two things. First, the answer to fib(4) is the sum of the answers to two smaller calls, fib(3) and fib(2). Each of those makes its own two calls, and so on, until the calls hit fib(1) and fib(0), which return 1 and 0 directly. Second, the same work shows up more than once. fib(2) is computed twice, once from fib(3) and once from fib(4). If this tree grows, the duplicated work explodes. That is the moment memoization becomes worth it, because caching each computed value removes the duplicates.
The other shape to know is linear recursion, where each call makes exactly one recursive call before combining. Walking down a linked list, or counting down to a base case, follows this shape. Its call stack grows and then shrinks in one straight line instead of a tree.
When to Use Recursion
Use recursion when you see these characteristics in the problem.
- The input has a natural nesting, like a tree, a linked list, or brackets inside brackets. Each nesting level is one smaller copy of the same task.
- An answer is built from answers to smaller versions of the same question. The Fibonacci sequence, tree depth, and expression evaluation all work this way.
- The problem asks you to enumerate every possibility, such as every subset, every permutation, or every valid placement of queens.
- The problem defines the answer position by position, where each position depends on earlier positions. Climbing stairs and K-th Symbol in Grammar are examples.
- The recursive version has an obvious iterative alternative, but that version needs its own explicit stack. When the natural stack is exactly what the data structure needs, recursion is the cleaner fit.
Complexity Analysis
The cost of a recursive solution depends on two numbers: how many calls happen in total, and how deep the stack grows. Deriving both from the structure of the recursion is more useful than memorizing them.
| Shape | Time | Space | Explanation |
|---|---|---|---|
| Linear recursion | O(N) | O(N) | One call per level, so N calls and a stack N deep |
| Tree recursion, no cache | O(2^N) | O(N) | Every call spawns two more, but the stack depth is still the path length |
| With memoization | O(N) | O(N) | Each distinct subproblem is solved once and stored |
| Backtracking | O(N!) | O(N) | Worst case explores every arrangement, one branch at a time |
The time derivation is a count of calls. A linear recursion makes N calls. A tree recursion like naive Fibonacci makes about 2^N calls, because the tree doubles at each level. Memoization changes the count: instead of recomputing the same subproblem many times, each distinct input is computed once, which brings the total down to O(N) distinct calls. Backtracking explores combinations, and the worst case is bounded by the number of arrangements, which is factorial for ordering problems.
The space derivation is a count of stack frames. Every pending call holds its own frame, so space is the maximum depth of the recursion, not the total number of calls. A chain of N calls is N deep. A tree recursion still only goes N deep, because the calls at the same level share the stack. Memoization adds a cache of size O(N).
Common Mistakes
Forgetting the base case. Without a base case, the function calls itself forever and the stack overflows. The base case is not decoration. It is the only thing that stops the calls. To catch this during practice, ask what the smallest input is and trace what happens when the recursion reaches it.
Writing a base case that is slightly wrong. Returning the right value for the wrong input size is a classic off-by-one. With Fibonacci, fib(0) must return 0 and fib(1) must return 1. With Climbing Stairs, ways(1) is 1 and ways(2) is 2. Test the first three inputs by hand before touching the recursive case.
Recursing without shrinking the input. If the recursive call passes the same value instead of a smaller one, the base case is never reached. Each call must move closer to the base case, usually by subtracting one or by moving a pointer forward.
Not combining the children’s results. The whole point of the recursive case is to combine the answers from the smaller calls. Forgetting the + 1 when computing tree depth, or returning only the left branch, produces a wrong answer that looks plausible. Trace a small tree and check that every level contributes its own value.
Related Patterns
- Backtracking . Backtracking is recursion with an undo step. It explores one branch, undoes the choice, and tries the next branch. The recursion page covers the skeleton; the backtracking page covers pruning and constraint checking.
- Divide and Conquer . Divide and conquer is recursion where the combination step is the interesting part. Merge sort splits the input in half and merges the sorted results.
- Tree Traversal . Tree traversal is recursion applied to a tree shape. The concept page there covers preorder, inorder, and postorder, which are the same recursive skeleton with different ordering of the combine step.
- Dynamic Programming . Dynamic programming starts from the memoized recursion on this page and removes the recursion entirely by filling a table bottom-up.
Next Steps
Once the concept is clear, the next step is making the code automatic. Check out the code templates for memorizable implementations in 6 languages, then work through the practice problems to apply the pattern to real interview questions.