Recursion

Recursion is the process of a function calling itself. It can break a complex problem into smaller versions of the same problem, but it can also create repeated work and a growing call stack.

Two parts of recursion

A recursive function usually needs two parts:

• Base case: stop recursing and return a direct result.
• Recursive case: make the problem smaller and call itself.

Without a base case, the function calls itself forever until the call stack overflows.

#include <cstdio>

void tell_story(void) {
    std::printf("Once upon a time...\n");
    std::printf("There was an old monk in a temple.\n");
    std::printf("The old monk told a young monk a story:\n");
    tell_story();
}

Factorial

Factorial is a classic first recursion example.

#include <cstdio>

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

int main() {
    std::printf("5! = %ld\n", factorial(5));
    return 0;
}

Output:

5! = 120

factorial(5) first calls factorial(4), then factorial(3), until it reaches factorial(1). Only then do the results return upward.

Ackermann's Function

Ackermann's function is a classic recursion example. Unlike factorial, it chooses different recursive branches based on both m and n.

#include <cstdio>

long ackermann(long m, long n) {
    if (m == 0) {
        return n + 1;
    }
    if (n == 0) {
        return ackermann(m - 1, 1);
    }
    return ackermann(m - 1, ackermann(m, n - 1));
}

int main() {
    std::printf("%ld\n", ackermann(2, 2));
    return 0;
}

Output:

7

This function grows extremely fast. As a beginner, only try very small inputs.

The table below shows m = 0…3 and n = 0…4. The first three rows grow gently, but at m = 3 each step to the right almost doubles the preceding result before adding more:

The table stops before m = 4: it jumps from A(4,0) = 13 to A(4,1) = 65533, and the following entry is already impractical to calculate or display directly.

The cost of recursion

Recursive code can be concise, but every recursive call creates a function call. For large inputs, this can be slow or even overflow the stack.

#include <cstdio>

long fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return fibonacci(n - 2) + fibonacci(n - 1);
}

int main() {
    std::printf("%ld\n", fibonacci(7));
    return 0;
}

Output:

13

This version repeats many calculations. For example, both fibonacci(5) and fibonacci(4) eventually compute fibonacci(3).

Tower of Hanoi

Some problems are naturally recursive. Tower of Hanoi can be described as:

1. Move the top n - 1 disks from source to helper.
2. Move the largest disk from source to destination.
3. Move the n - 1 disks from helper to destination.

#include <cstdio>

int move = 0;

void hanoi(int n, char src, char mid, char dst) {
    if (n == 1) {
        std::printf("%c -> %c\n", src, dst);
        move++;
    } else {
        hanoi(n - 1, src, dst, mid);
        std::printf("%c -> %c\n", src, dst);
        move++;
        hanoi(n - 1, mid, src, dst);
    }
}

int main() {
    hanoi(3, 'A', 'B', 'C');
    std::printf("Moves: %d\n", move);
    return 0;
}

Output:

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
Moves: 7

Each visible move moves one disk, but the recursive task first moves the top n - 1 disks.

Recursion is not meant to look advanced. It helps express problems that already have a self-similar structure.