Recursion

Recursion is when a function calls itself to solve a smaller version of the same problem. Every well-formed recursive function needs two essential parts: a base case that stops the recursion, and a recursive case that makes progress toward that base case.

Base Case and Recursive Case

The base case is the simplest version of the problem, one the function can answer directly without calling itself again. The recursive case breaks the problem down and calls the function again on a smaller piece of it. Without a correctly reachable base case, a recursive function calls itself forever.

Classic Example: Factorial

The factorial of n (written n!) is n × (n-1) × (n-2) × ... × 1, with the special case that 0! is defined as 1. That definition maps directly onto a base case and a recursive case.

CPP

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n <= 1) {
        return 1; // base case
    }
    return n * factorial(n - 1); // recursive case
}

int main() {
    cout << factorial(5) << endl; // Output: 120
    return 0;
}
// factorial(5)
//   = 5 * factorial(4)
//   = 5 * (4 * factorial(3))
//   = 5 * (4 * (3 * factorial(2)))
//   = 5 * (4 * (3 * (2 * factorial(1))))
//   = 5 * 4 * 3 * 2 * 1 = 120

Classic Example: Fibonacci

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, ...) is another textbook recursive definition: each number is the sum of the two before it, with the first two numbers as base cases.

CPP

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) {
        return n; // base cases: fib(0) = 0, fib(1) = 1
    }
    return fibonacci(n - 1) + fibonacci(n - 2); // recursive case
}

int main() {
    for (int i = 0; i < 10; i++) {
        cout << fibonacci(i) << " ";
    }
    cout << endl;
    // Output: 0 1 1 2 3 5 8 13 21 34
    return 0;
}

Note

This naive Fibonacci implementation recomputes the same values many times and grows exponentially slower as n increases. It's a great teaching example, but real code would use memoization or an iterative loop for anything beyond small inputs.

Stack Overflow Risk

Every recursive call adds a new frame to the program's call stack, holding that call's local variables and return address. The call stack has a finite size.

Warning

C++ has no built-in recursion depth limit or safety net like Python's clean, catchable RecursionError. If recursion goes too deep, the program exhausts its call stack and crashes with a stack overflow — and in C++, that is undefined behavior, not a well-defined exception. There is no guarantee of a clean error message; the program may simply crash, or in rare cases corrupt memory silently. Always ensure your base case is reachable and your recursion depth is bounded to something the stack can handle.

CPP

// Dangerous: no base case, or a base case that's never reached.
int badCountdown(int n) {
    cout << n << endl;
    return badCountdown(n - 1); // never stops - eventually crashes
}

// Safe: base case guarantees termination.
int goodCountdown(int n) {
    if (n <= 0) {
        cout << "Liftoff!" << endl;
        return 0;
    }
    cout << n << endl;
    return goodCountdown(n - 1);
}

Tail Recursion

A recursive call is a tail call when it is the very last action a function performs, with nothing left to do after it returns. Some languages guarantee that tail calls are optimized into a loop, reusing the same stack frame instead of growing the stack.

Note

In C++, tail call optimization is implementation-defined, not guaranteed by the standard. A compiler with optimizations enabled (-O2 and above) will often turn a clean tail-recursive function into an efficient loop, but you cannot rely on this happening — without it, deep tail recursion still risks a stack overflow exactly like any other recursion.

CPP

// Tail-recursive style: the recursive call is the last thing that happens.
int factorialTail(int n, int accumulator = 1) {
    if (n <= 1) {
        return accumulator;
    }
    return factorialTail(n - 1, n * accumulator); // tail call
}

When to Prefer Iteration

For performance-critical code, or recursion whose depth scales with input size (and could plausibly be large), an iterative loop is usually the safer and often faster choice — it uses constant stack space and avoids relying on an optimization the compiler may or may not perform.

CPP

// Iterative factorial: no recursion, no stack growth, no overflow risk.
int factorialIterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Tip

Use recursion when it makes an algorithm clearer to express (tree traversal, divide-and-conquer, backtracking). Prefer iteration when the recursion depth could be large and unbounded, or when raw performance matters more than expressive clarity.

Key Points

Every recursive function needs a reachable base case and a recursive case that progresses toward it.
Factorial and Fibonacci are classic examples of problems with a natural recursive definition.
C++ has no built-in recursion depth limit; excessive recursion causes a stack overflow, which is undefined behavior.
Tail call optimization in C++ is implementation-defined, not guaranteed by the standard.
Prefer iteration over deep recursion when performance or stack safety is a concern.