Recursion

Recursive definitions

The factorial

The factorial of a natural number $n$ is the product of the natural numbers from 1 to $n$: $n! = 1 \cdot 2 \cdots n$, with the convention $0! = 1$. The ellipsis in that formula hides a loop, and the lesson Loops taught how to write it. Now, the same definition admits another form, which mentions no loop: the factorial of $n$ is $n$ times the factorial of $n - 1$, and that of 0 is 1.

This is a recursive definition: it defines the factorial of $n$ by means of the factorial of a smaller number. It is not circular, because each application of the second rule goes down one step and the staircase ends at the first: $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$. The two rules have names. The first is the base case, which gives the result without referring to anything else; the second is the recursive case, which reduces the problem to a smaller instance of the same problem.

C++ allows a function to call itself, and with that the definition translates almost word for word.

#include <print>​// Factorial of n.// Precondition: 0 <= n <= 12 (the bound is justified further on).// Postcondition: returns n! = 1 · 2 · ... · n, with 0! = 1.int factorial(int n){    if (n == 0) {        return 1;                   // base case    }    return n * factorial(n - 1);    // recursive case}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

0! = 11! = 12! = 23! = 64! = 245! = 1206! = 720

The contract is not decorative: with $n = -1$ the recursive case would call with $-2$, then with $-3$, and would never reach 0; and $13!$ does not fit in an int. Many introductory texts write this factorial with the base case if (n == 0 || n == 1), redundant but harmless, and without saying anything about negative numbers or about the size of the result: their code does not terminate with $n < 0$ and gives a meaningless result from $13!$ on. Both defects will be examined in their own section.

Base case and recursive case

Every recursive function has one or more base cases, which are solved directly, and one or more recursive cases, which call the same function with an argument that is smaller in some precise sense and combine what it returns.

The power $x^n$, with $n$ natural, is defined by $x^0 = 1$ and $x^n = x \cdot x^{n - 1}$: the size is the exponent. The sum of the digits of a natural number $n$ (that of 2026 is $2 + 0 + 2 + 6 = 10$) is defined as follows: if $n < 10$, the sum is $n$, because it has a single digit; otherwise, it is the sum of the digits of $\lfloor n / 10 \rfloor$, which is $n$ without its last digit, plus that last digit, $n \bmod 10$. Here the size is the number of digits.

#include <print>​// x raised to n.// Precondition: n >= 0.// Postcondition: returns x^n, with x^0 = 1.double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// Sum of the decimal digits of n.// Precondition: n >= 0.// Postcondition: returns the sum of the digits of n.int digitSum(int n){    if (n < 10) {        return n;    }    return digitSum(n / 10) + n % 10;}​int main(){    std::println("2^10 = {}", power(2.0, 10));    std::println("1.5^3 = {}", power(1.5, 3));    std::println("sum of the digits of 2026: {}", digitSum(2026));}

2^10 = 10241.5^3 = 3.375sum of the digits of 2026: 10

Writing a recursive function therefore consists in answering two questions: which cases are solved without help, and how the solution of a case is obtained from that of a smaller one. If both answers are correct, so is the function, and the next section proves it.