recursion
Stand between two mirrors and you see an image of an image of an image, shrinking toward the middle. Recursion is a function defined partly in terms of itself: to solve a problem, it solves a smaller version of the same problem and builds on that answer. As long as each step shrinks the problem and there is a smallest case that stops the regress, the whole thing terminates.
A recursive function needs two parts: a base case that returns a direct answer without recursing (the stopping condition), and a recursive case that calls itself on a smaller input and combines the result. Factorial is the textbook example: factorial(0) is 1 (base case), and factorial(n) is n times factorial(n - 1) (recursive case). Each call gets its own stack frame holding its own copy of n, so the calls stack up — factorial(3) waits on factorial(2), which waits on factorial(1), which waits on factorial(0) — and then the answers unwind back up the chain.
Why this matters and the honest caveat: recursion expresses naturally self-similar problems — trees, nested structures, divide-and-conquer algorithms — far more clearly than loops. But every pending call consumes a stack frame, so a missing or wrong base case, or a recursion that is simply too deep, overflows the call stack and crashes (a stack overflow). Recursion is also not free: in C, a loop is often cheaper than deep recursion because it avoids the per-call overhead and the stack growth.
long factorial(int n) { if (n <= 1) return 1; /* base case: stops recursing */ return n * factorial(n - 1); /* recursive case: smaller input */ } /* factorial(4) -> 4*3*2*1 -> 24 */
The base case n <= 1 stops the regress; the recursive case shrinks n each time. Each pending call keeps its own stack frame.
A missing or incorrect base case, or recursion that is simply too deep, overflows the call stack and crashes. Recursion is not free in C — each call costs a stack frame and overhead, so a loop is often the cheaper choice.