Thinking Recursively

A function that calls itself

Recursion solves a problem by solving a smaller version of the same problem. In code, it's a function that calls itself.

Think of it like this: You're in a long queue and want your position. You ask the person in front, who asks the person in front of them... The first person says “1” (the base case). Each person adds 1 and passes it back.

#include <iostream>
using namespace std;

void countdown(int n) {
    if (n == 0) {               // base case
        cout << "Lift off!" << endl;
        return;
    }
    cout << n << endl;
    countdown(n - 1);           // smaller problem
}

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

Output

3
2
1
Lift off!

• Base case – the smallest problem, answered directly.
• Recursive step – make the problem smaller and call again. Every call must get closer to the base case.

The call stack

Each call waits for the call it made. The waiting calls sit on the call stack:

#include <iostream>
#include <string>
using namespace std;

long long factorial(int n, int depth = 0) {
    string pad(depth * 2, ' ');
    cout << pad << "factorial(" << n << ") called" << endl;
    long long result = (n <= 1) ? 1 : n * factorial(n - 1, depth + 1);
    cout << pad << "factorial(" << n << ") returns " << result << endl;
    return result;
}

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

Output

factorial(3) called
  factorial(2) called
    factorial(1) called
    factorial(1) returns 1
  factorial(2) returns 2
factorial(3) returns 6

Common mistake: Without a base case the function calls itself until the stack runs out of space and the program crashes (a stack overflow).