Recursion

Solve a smaller version of the same problem.

A recursive function asks the same function to solve a smaller problem. A base case stops new calls. Each unfinished call then uses its child’s result and returns to its own caller. The recursive step must make progress toward the base case for the inputs the function accepts.

A base case only helps if you reach it.

A function can contain a correct-looking stop condition and still keep making calls. Starting from a positive integer, n - 1 approaches zero while n + 1 moves away. Reason about the allowed inputs and how every recursive step moves closer to a stopping case.

Every call keeps its own n.

sumTo(3) waits for sumTo(2), which waits for sumTo(1), which waits for zero. The returned values then build up as 0, 1, 3, and 6. The input limit keeps this small example away from integer overflow and excessive depth.

// Precondition: 0 <= n && n <= 100
int sumTo(int n) {
    if (n == 0) return 0;
    return n + sumTo(n - 1);
}
std::cout << sumTo(3);

Calls wait; results unwind.

At the deepest point, three callers are unfinished. The base case returns zero. Each caller resumes with its own n and adds it to the result it received. The arrows show calls going down; results return to the caller above.

Unfinished calls need state.

In this version, each unfinished invocation retains constant-sized state, such as its n and where to resume. A depth-n chain therefore uses linear auxiliary call space in the ordinary call-stack model. Recursion is not automatically faster or more memory-efficient than iteration.