Some problems contain smaller copies of themselves. A folder holds subfolders. A sentence holds clauses. A sorted half still needs sorting.
Recursion solves such problems directly. A recursive function calls itself with a smaller input, then combines the returned answer with its own work.
Every recursive function has two parts. Miss either one and the program breaks.
The two parts every recursive function needs
The base case is the input with a known answer. It stops the calls. Factorial defines 0! = 1 and never recurses below zero.
The recursive case calls the function again with input closer to the base case. It then builds the current answer from the smaller answer. Factorial defines n! = n × (n − 1)! for positive n.
Progress toward the base case is mandatory. A call that passes the same input down never terminates. A call that skips past the base case never lands on it.
Factorial shows both parts at work
The factorial of n, written n!, multiplies all positive integers up to n. The definition is already recursive: strip off n, solve the smaller product, multiply.
The same function in three languages:
// Return n x (n-1) x ... x 1 by delegating to smaller inputs. // factorial(0) is defined as 1. int factorial(int n) { // Base case: the smallest input has a known answer. if (n == 0) return 1; // Recursive case: n! = n x (n-1)!, so solve the smaller piece first. return n * factorial(n - 1); } // factorial(5) calls 4, 3, 2, 1, 0, then returns 120 up the chain.
Calling factorial(5) builds a chain of six calls. Each waits for the next. The base case returns 1. The pending calls then multiply on the way back: 1, 1, 2, 6, 24, 120.
See the full execution trace to watch each call and return in order.
The call stack keeps every waiting call
Each active call owns a stack frame. A stack frame is a small memory region holding the parameters, local variables, and return address of one call. Frames pile up on the call stack.
When factorial(5) calls factorial(4), both frames exist at once. The older frame waits. The newer frame runs. When factorial(0) returns, its frame is removed and the caller resumes.
Memory use therefore grows with depth. Computing factorial(n) keeps n frames alive at the deepest point. That is O(n) stack space for O(n) calls.
Depth has a hard limit. Each thread gets a fixed stack, often 8 MB. A chain of a million calls needs far more frames than fit. The program crashes with a stack overflow. Languages without tail-call optimization cannot compress such chains, so deep recursion needs an explicit stack or a loop instead.
Problems that fit the recursive shape
Recursion shines where the data or the task is self-similar. The code then mirrors the structure instead of fighting it.
| Problem | Recursive view |
|---|---|
| Fibonacci numbers | fib(n) = fib(n - 1) + fib(n - 2) with known answers at 0 and 1 |
| Tree traversal | visit a node, then solve the left and right subtrees the same way |
| Merge sort | sort each half, then merge two sorted halves |
| Graph walk | visit a node, then visit each unvisited neighbor the same way |
| Binary search | check the middle, then search the half that can hold the target |
Trees show the clearest win. A tree node holds smaller trees by definition. A recursive traversal visits the node and recurses into each child. The iterative version needs a manual stack that restates what the call stack already does.
Divide and conquer shows the performance win. Each level splits the work into independent pieces. The recurrence for the running time then follows the same shape as the code.
Three mistakes that break recursive code
The first mistake is a missing base case. The function calls itself forever. Frames pile up until the stack overflows. Every recursive function deserves its termination argument written down first.
The second mistake is a recursive call that makes no progress. Calling factorial(n) from inside factorial(n) loops on the same input. Check that each call moves strictly closer to the base case.
The third mistake is solving the same subproblem many times. Naive Fibonacci recomputes fib(30) thousands of times on the way to fib(40). The call count grows exponentially even though only 41 distinct answers exist.
The fix is memoization. Memoization stores each computed answer in a table and reuses it. The exponential tree of calls collapses into a linear sequence of distinct states. A bottom-up loop that fills the table from the base case upward achieves the same saving without recursion at all.
A fourth hazard deserves attention. Recursion depth follows the data, not the code. A balanced tree of a million nodes needs about 20 levels. A degenerate chain of the same nodes needs a million. Size your approach for the worst shape the input can take.
Where recursion runs and what to read next
Recursion walks file systems and document trees. It parses expressions and compiles nested syntax. It traverses graphs and backtracks through search spaces. Compilers, databases, and game engines all lean on it.
It also teaches a transferable skill. Breaking a task into a smaller copy plus a combining step works for proofs, tests, and system designs too.
Try recursive Fibonacci with and without memoization to feel the exponential-to-linear gap. The climbing-stairs practice turns that lesson into a dynamic programming exercise. Then read what an algorithm is to connect base cases with invariants.