C++ Recursion

C++ recursion is when a function calls itself to solve a problem in smaller steps. Every recursive function needs a stopping condition, called a base case, so the calls do not continue forever.

Recursion is useful when a task naturally repeats on a smaller value, such as counting down, adding numbers in a range, or calculating a factorial.

How Recursion Works

A recursive function usually has two important parts:

• A base case, which gives an answer without making another recursive call.
• A recursive case, which calls the same function with a smaller or simpler argument.

If the recursive case does not move closer to the base case, the program can keep calling the function until it runs out of stack memory.

Countdown Example

This function prints a number, then calls itself with a smaller number. When the number reaches 0, the base case prints Done and returns.

#include <iostream>

void countDown(int number) {
    if (number == 0) {
        std::cout << "Done" << std::endl;
        return;
    }

    std::cout << number << std::endl;
    countDown(number - 1);
}

int main(void) {
    countDown(3);

    return 0;
}

Output:

3
2
1
Done

The call countDown(3) prints 3, then calls countDown(2). The same pattern continues until countDown(0) reaches the base case.

Returning A Recursive Result

Recursive functions can return values too. The next example calculates the sum of all whole numbers from 1 to n.

#include <iostream>

int sumTo(int n) {
    if (n == 1) {
        return 1;
    }

    return n + sumTo(n - 1);
}

int main(void) {
    std::cout << sumTo(5) << std::endl;

    return 0;
}

Output:

15

The expression sumTo(5) becomes 5 + sumTo(4). Then sumTo(4) becomes 4 + sumTo(3), and so on. When sumTo(1) returns 1, C++ finishes the waiting function calls in reverse order and adds the values together.

Factorial Example

A factorial multiplies a number by each positive whole number below it. For example, 4! means 4 * 3 * 2 * 1.

#include <iostream>

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }

    return n * factorial(n - 1);
}

int main(void) {
    std::cout << factorial(4) << std::endl;
    std::cout << factorial(6) << std::endl;

    return 0;
}

Output:

24
720

The base case handles n <= 1. For larger values, the function multiplies n by the factorial of the next smaller number.

Recursion And The Call Stack

Each function call uses a small amount of memory on the call stack. A recursive function creates a new stack frame every time it calls itself. After the base case is reached, those calls finish one by one in reverse order.

Because recursive calls use stack memory, recursion is not always the best choice for very large counts. For simple repeated work, a loop may be clearer and use less memory.

Common Mistakes

• Forgetting the base case.
• Writing a base case that the function can never reach.
• Calling the function with the same value instead of a smaller or simpler value.
• Using recursion when a simple loop would be easier to read.

Takeaway: C++ recursion lets a function solve a problem by calling itself, but each call must move closer to a clear base case.