5.3 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 <iostream>

void tell_story() {
    std::cout << "Once upon a time..." << std::endl;
    tell_story();
}

Factorial

Factorial is a classic first recursion example.

#include <iostream>

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

int main() {
    std::cout << "5! = " << factorial(5) << std::endl;
    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 does not simply subtract 1 from n; it chooses different recursive branches based on both m and n.

#include <iostream>

int ackermann(int m, int 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::cout << ackermann(2, 2) << std::endl;
    return 0;
}

Output:

7

This function is useful for seeing recursion nested inside recursion, but it grows extremely fast. As a beginner, only try very small inputs such as ackermann(2, 2) or ackermann(3, 1).

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 <iostream>

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

int main() {
    std::cout << fibonacci(7) << std::endl;
    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 the source peg to the helper peg.

2. Move the largest disk from the source peg to the destination peg.

3. Move the n - 1 disks from the helper peg to the destination peg.

#include <iostream>

int move_count = 0;

void hanoi(int n, char src, char mid, char dst) {
    if (n == 1) {
        std::cout << src << " -> " << dst << std::endl;
        move_count++;
    } else {
        hanoi(n - 1, src, dst, mid);
        std::cout << src << " -> " << dst << std::endl;
        move_count++;
        hanoi(n - 1, mid, src, dst);
    }
}

int main() {
    hanoi(3, 'A', 'B', 'C');
    std::cout << "Moves: " << move_count << std::endl;
    return 0;
}

Output:

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

Each visible move moves only one disk, but the recursive task is "move the top n - 1 disks first, then move the largest disk." Use the lab below to step through the three pegs.

Recursion is not for looking clever. It is useful when a problem has a naturally self-similar structure.