Recursion
A function that calls itself to solve a problem by breaking it into smaller sub-problems. Needs a base case to stop. Used for tree traversal, divide-and-conquer algorithms, and problems with a recursive structure. Can stack-overflow without tail-call optimization.
- Tree/graph traversal.
- Divide-and-conquer (merge sort, quicksort).
- Problems with recursive structure.
- Simple iteration (a loop is clearer).
- Very deep recursion without TCO.
Definition
Recursion is when a function calls itself. Each call works on a smaller input until a base case returns without recursing. The calls unwind, combining results. Without a base case, it loops infinitely and stack-overflows.
Why it exists
Some problems (tree traversal, factorial, Fibonacci, parsing) are naturally recursive. Recursion expresses them more clearly than loops.
How it works
Function checks: is this the base case? If yes, return the trivial answer. If no, call itself with a smaller input and combine the result. Each call adds a stack frame; deep recursion can overflow the stack. Tail-call optimization (not in JS/Python) reuses the frame.
Scaling limits
Stack overflow on deep recursion (no TCO in most languages). Each call uses memory. Very deep recursion needs conversion to iteration or explicit stack.
Cost shape
Free.
Alternatives
- Iteration (loops) — No stack overflow but can be less clear for recursive problems.
- Explicit stack — Manual but avoids stack overflow.
Failure modes
- Missing base case → infinite recursion → stack overflow.
- Deep recursion without TCO.
- Redundant recomputation (memoize!).