C++ Recursion
Recursion is when a function calls itself to solve a smaller instance of the same problem, eventually reaching a base case that stops the recursion. Classic examples include factorial, Fibonacci, and tree/graph traversal.
Every recursive function needs a base case (to stop) and a recursive case (that makes progress toward the base case) — without both, you get infinite recursion and a stack overflow.
Base case and recursive case
The base case returns a direct answer without calling itself again (e.g. factorial(0) = 1). The recursive case reduces the problem size, e.g. `n * factorial(n-1)`.
Recursion vs loops
Recursion is often more elegant for tree-like or divide-and-conquer problems, but each call uses stack memory, so very deep recursion can crash with a stack overflow.
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
int main() {
std::cout << factorial(5);
}120factorial(5) calls factorial(4)...factorial(0), which returns 1 to stop the chain.
Key points
- Every recursive function needs a base case.
- The recursive case must move toward the base case.
- Deep recursion risks a stack overflow.
- Recursion suits divide-and-conquer and tree problems.