recursion
Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. The picture to hold in your head is a set of nesting dolls: to open the biggest doll you open a slightly smaller one inside it, and that one contains a smaller one still, until you reach the tiniest doll that opens to nothing. That tiniest doll is the key idea — every correct recursion has a base case, a situation simple enough to answer outright with no more calls, and a recursive case that does a little work and then defers the rest to a smaller call. "What is the factorial of 4?" becomes "4 times the factorial of 3", which becomes "4 times 3 times the factorial of 2", and so on down to the factorial of 0, which we simply declare to be 1.
Mechanically, each call gets its own little workspace — its own copy of the local variables — stacked on top of the previous one in a region of memory called the call stack. The computer dives down, piling up unfinished calls, until it hits a base case; then it unwinds, finishing each pending call on the way back up and handing its answer to the one that was waiting. If you forget the base case (or never actually move toward it), the stack keeps growing until the program crashes with a stack overflow — recursion's most famous failure mode.
Recursion is a way of thinking, not a free lunch. A naive recursion can re-solve the same subproblem over and over: computing the nth Fibonacci number by the obvious two-call recursion branches exponentially, doing roughly O(2^n) work for something that needs only O(n). The fix is to remember answers you have already computed (memoization) or to turn the recursion inside-out into a loop that fills a table (dynamic programming). Recursion is also the natural language for divide-and-conquer and for walking tree and graph structures.
int fib(int n) {
if (n < 2) return n; // base case
return fib(n - 1) + fib(n - 2); // recursive case (branches!)
}
// fib(4)
// / \
// fib(3) fib(2)
// / \ / \
// fib(2) fib(1) fib(1) fib(0)
// / \
// fib(1) fib(0)The same subproblem appears on several branches — exactly the waste memoization removes.
Every recursion can in principle be rewritten as a loop using an explicit stack, and vice versa. Some languages optimise a special case — tail recursion, where the recursive call is the very last thing the function does — into a plain loop that uses no extra stack; C++ compilers may do this but are not required to, so don't rely on it for unbounded depth.