Programming · intermediate
Recursion
Recursion is a computation in which a function or definition refers to itself directly or through other functions. A terminating recursive algorithm needs reachable stopping cases and recursive steps that make progress toward them.
Why it matters
Recursive structure naturally models trees, divide-and-conquer algorithms, grammars, graph search, and nested data. Understanding its state and depth helps choose between recursion, iteration, and an explicit stack.
Mental model
How to reason about recursion
Each active call owns a smaller subproblem and waits for its recursive result, usually in a separate call frame. The base case returns without another recursive call, allowing pending frames to complete in reverse order.
Analogy
Recursion is a stack of delegated questions: each person asks a simpler version and waits, until one person can answer directly and the answers travel back up the chain.
Examples
See the boundary, not just the happy path
Worked example · Recursive factorial
def factorial(n):
if n < 0: raise ValueError()
if n <= 1: return 1
return n * factorial(n - 1)For non-negative n, each call decreases n and reaches the base case. The explicit negative-input check prevents values that move forever away from that stopping condition.
Worked example · Walk a binary tree
visit(node.left); process(node); visit(node.right)With a null-node base case, the recursive call structure mirrors the tree's nested structure. Maximum call depth follows tree height, which can be linear for a highly unbalanced tree.
Useful contrast · Iteration can hold the state explicitly
Use a loop with a stack collection for a deep tree traversalThis is the same traversal strategy with pending work stored in a separately managed collection whose capacity is not tied to one runtime call frame per level, avoiding the runtime's call-stack depth limit.
Common mistakes
Misconceptions to remove early
Having a base case that inputs never approach
A base case is useful only if every intended recursive path makes progress toward it. Validate domains and identify a decreasing measure or other termination argument.
Assuming tail calls always use constant stack space
Some languages or runtimes guarantee tail-call optimization and others do not. A syntactically tail-recursive function can still consume one frame per call without that guarantee.
Quick check
Can you predict the result?
1. What two properties support termination of a recursive algorithm?
- • A reachable stopping case and recursive steps that make progress toward it.
- • A global variable and at least two parameters.
- • A compiler and a garbage collector.
2. Why can an explicit stack handle a traversal that overflows the call stack?
Keep building