A recursive function calls itself. It sounds circular; it works because each call is a separate stack frame (lesson 5.2) working on a smaller problem.

#include <iostream>

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

int main() {
    std::cout << factorial(5) << "\n";
    std::cout << factorial(1) << "\n";
    std::cout << factorial(0) << "\n";
    return 0;
}

120
1
1

Tracing factorial(5):

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)))          ← base case reached
               120

Five frames stack up, then unwind as each returns.

Every recursion needs two things

A base case — a condition that returns without recursing. This is what ends it.

A recursive case that moves toward the base case. factorial(n - 1) gets smaller each time, so it must eventually reach 1.

Miss either and the recursion never ends:

int broken(int n) {
    return n * broken(n - 1);   // no base case — runs until the stack dies
}

Called with 5, that goes 5, 4, 3, 2, 1, 0, −1, −2… forever. Not an infinite loop — an infinite descent, each level consuming a stack frame.

Stack overflow

The stack is finite (lesson 5.2), so infinite recursion doesn't hang — it crashes:

Segmentation fault (core dumped)

That's stack overflow: the program ran out of stack and the OS killed it. Typical depth before that happens is tens to hundreds of thousands of frames, depending on frame size and the platform's stack limit.

Even correct recursion has this limit. A function that recurses once per element will die on a list of ten million.

Recursion is not free

Each level costs a stack frame and the overhead of a call. Compare:

#include <iostream>

long long sum_to_recursive(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sum_to_recursive(n - 1);
}

long long sum_to_iterative(int n) {
    long long total = 0;          // int would overflow well before a million
    for (int i = 1; i <= n; ++i) {
        total += i;
    }
    return total;
}

int main() {
    std::cout << sum_to_recursive(100) << "\n";
    std::cout << sum_to_iterative(100) << "\n";
    std::cout << sum_to_iterative(1000000) << "\n";
    return 0;
}

5050
5050
500000500000

Same answers for 100. But the iterative version handles a million with one stack frame and a counter; the recursive one would very likely crash.

Note the long long. The sum to a million is 500,000,500,000 — far past what an int holds, so returning int here would silently overflow (lesson 3.3) and print garbage. Recursion depth isn't the only limit worth checking.

When the problem is naturally linear, use a loop. Recursion earns its cost on problems that are naturally branching — trees, nested structures, divide and conquer.

Where recursion genuinely wins

Anything with nested structure. Here's a directory-tree-shaped problem — the iterative version would need an explicit stack, which is just recursion written out by hand:

#include <iostream>
#include <string>
#include <vector>

struct Node {
    std::string name;
    std::vector<Node> children;
};

int count_nodes(const Node& node) {
    int count = 1;
    for (const Node& child : node.children) {
        count += count_nodes(child);
    }
    return count;
}

void print_tree(const Node& node, int depth = 0) {
    std::cout << std::string(depth * 2, ' ') << node.name << "\n";
    for (const Node& child : node.children) {
        print_tree(child, depth + 1);
    }
}

int main() {
    Node tree{"root", {
        Node{"src", {Node{"main.cpp", {}}, Node{"util.cpp", {}}}},
        Node{"docs", {Node{"readme.md", {}}}}
    }};

    print_tree(tree);
    std::cout << "total nodes: " << count_nodes(tree) << "\n";
    return 0;
}

root
  src
    main.cpp
    util.cpp
  docs
    readme.md
total nodes: 6

Six lines of recursion handle arbitrary nesting depth. That's the case for it.

Note the default argument int depth = 0 (lesson 5.5) letting the caller write print_tree(tree) while the recursion passes depth + 1 internally — a very common pairing.

The classic trap: naive Fibonacci

#include <iostream>

long long fib_slow(int n) {
    if (n <= 1) {
        return n;
    }
    return fib_slow(n - 1) + fib_slow(n - 2);
}

long long fib_fast(int n) {
    long long previous = 0;
    long long current = 1;
    if (n == 0) {
        return 0;
    }
    for (int i = 2; i <= n; ++i) {
        long long next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}

int main() {
    std::cout << fib_slow(20) << "\n";
    std::cout << fib_fast(20) << "\n";
    std::cout << fib_fast(90) << "\n";
    return 0;
}

6765
6765
2880067194370816120

fib_slow is the textbook recursion example and it's terrible. Each call spawns two more, so the work roughly doubles per level — fib_slow(50) would take longer than you'll wait. It recomputes fib(10) thousands of times.

fib_fast is a loop doing n additions. It handles 90 instantly.

The lesson isn't "recursion is slow" — it's that recursion makes it easy to accidentally write an exponential algorithm. When branches recompute the same subproblems, either memoize the results or use a loop.

Try it

Checkpoint

• A recursive function calls itself; each call is a separate stack frame.
• Every recursion needs a base case and a recursive case that moves toward it.
• Missing either causes stack overflow — a crash, not a hang.
• Even correct recursion is limited by stack depth; deep linear recursion should be a loop.
• Recursion earns its cost on branching, nested structures: trees, parsers, divide and conquer.
• Branching recursion that recomputes subproblems (naive Fibonacci) is exponential — memoize or iterate.