Definition
Recursion is a process or definition that refers to itself. A recursive procedure handles its input by handling a smaller version of the same input, combining the result with a small amount of work specific to the current step. A recursive definition specifies a quantity in terms of itself on smaller arguments — n! = n × (n-1)! with the base case 0! = 1.
Recursion is the structural backbone of language (a sentence can contain a sentence), music (a phrase can contain a phrase), computer programs (a function can call itself), biology (a chromosome contains genes that synthesize the machinery that copies the chromosome), and physics' renormalization schemes.
Why it matters
How it works
A recursive procedure has three parts. Base case: the simplest input, handled directly. Recursive case: a step that handles the current input by calling itself on a smaller input. Combination: the rule for combining the recursive result with the current step's local work.
Examples: factorial computes n! by multiplying n by (n-1)!, bottoming out at 0! = 1. Tree traversal handles a tree by handling each subtree and combining results. Fibonacci computes F(n) as F(n-1) + F(n-2), bottoming at F(0) = 0, F(1) = 1.
Recursion always works because the calls terminate at the base case. If your recursive call does not make progress toward the base case, the recursion does not terminate. Memoization (caching results of recursive calls) can turn exponential recursion into linear iteration when subproblems are reused.