Recursion

A function can call other functions. It can also call itself. A function that calls itself is called recursive, and the idea is called recursion.

#include <iostream>
using namespace std;

void countdown(int n) {
    if (n == 0) {
        cout << "Go!" << "\n";
        return;
    }
    cout << n << "\n";
    countdown(n - 1);
}

int main() {
    countdown(3);
    return 0;
}

Output:

3
2
1
Go!

Follow the calls one by one. countdown(3) prints 3 and calls countdown(2). That call prints 2 and calls countdown(1), which prints 1 and calls countdown(0). Now n is 0, so the function prints Go! and returns. A return; with no value simply ends a void function.

Every recursive function needs two parts:

  • A base case: an input where the function stops without calling itself. Here it is n == 0.
  • A recursive case: the function does a small part of the work, then calls itself with a smaller input. Here it calls countdown(n - 1).

If the base case is missing, or the input never gets smaller, the function keeps calling itself. Each call that has not finished yet uses some memory. After enough calls, the program runs out of that memory and crashes with a "Segmentation fault" error. Unlike an endless loop, it does not run forever. (If the function prints in every call, like countdown, the code runner may stop it first with "Output limit exceeded".)

Recursion with a return value

A recursive function can also return a value. This one adds all the numbers from 1 to n:

#include <iostream>
using namespace std;

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

int main() {
    cout << sumTo(4) << "\n";
    return 0;
}

Output:

10

The sum of 1 to 4 is 4 plus the sum of 1 to 3. That is exactly what the line return n + sumTo(n - 1); says. The calls go down until the base case:

sumTo(4) = 4 + sumTo(3)
sumTo(3) = 3 + sumTo(2)
sumTo(2) = 2 + sumTo(1)
sumTo(1) = 1 + sumTo(0)
sumTo(0) = 0

Then the answers come back up: sumTo(1) is 1, sumTo(2) is 3, sumTo(3) is 6, and sumTo(4) is 10.

When to use it

Both examples here would be just as easy with a loop, and in real code a loop is the better choice for them. Recursion is most useful when the data has the same shape inside itself. For example, a folder can hold files and other folders, and each of those folders can hold more folders. A recursive function can handle one folder and call itself for each folder inside it.

The factorial of n is n * (n - 1) * ... * 1, so the factorial of 5 is 120. It also has the same shape as sumTo: the factorial of n is n times the factorial of n - 1. In the exercise, the base case is ready. Write the recursive case.