Recursion: Functions That Call Themselves

A function can call itself. This is called recursion. It's a way to solve a big problem by solving a smaller version of the same problem.

Think of it like this: Russian dolls: to find the smallest doll, open the doll. Inside there's a smaller doll – do the same thing again. Stop when a doll doesn't open. That last doll is the base case.

#include <iostream>
using namespace std;

void countdown(int n) {
    if (n == 0) {              // base case: stop here
        cout << "Lift off!\n";
        return;
    }
    cout << n << "\n";
    countdown(n - 1);          // the same job, one step smaller
}

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

Output

3
2
1
Lift off!

Factorial

The factorial of 5 (written 5!) is 5 × 4 × 3 × 2 × 1 = 120. Notice that 5! = 5 × 4!. That makes it perfect for recursion:

#include <iostream>
using namespace std;

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

int main() {
    for (int i = 1; i <= 6; i++) {
        cout << i << "! = " << factorial(i) << "\n";
    }
    return 0;
}

Output

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720

Common mistake: Forgetting the base case. Without it the function calls itself forever, until the program runs out of memory and crashes.

Tip: Anything you can do with recursion you can also do with a loop. Use whichever makes the code clearer.