递归

递归定义

阶乘

自然数 $n$ 的阶乘是从 1 到 $n$ 的各个自然数之积：$n! = 1 \cdot 2 \cdots n$，并约定 $0! = 1$。这个公式中的省略号藏着一个循环，循环一课已经教过怎样写它。然而，同一个定义还有另一种形式，其中不提任何循环：$n$ 的阶乘等于 $n$ 乘以 $n - 1$ 的阶乘，而 0 的阶乘等于 1。

这是一个递归定义：它借助一个更小的数的阶乘来定义 $n$ 的阶乘。它并不循环论证，因为第二条规则每用一次就下降一级台阶，而台阶终止于第一条规则：$3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$。这两条规则都有名字。第一条是基本情形，它不借助任何别的东西就给出结果；第二条是递归情形，它把问题归结为同一问题的一个更小的实例。

C++ 允许函数调用自身，因此这个定义几乎可以逐字翻译过来。

#include <print>​// n 的阶乘。// 前置条件：0 <= n <= 12（这个上界在后面论证）。// 后置条件：返回 n! = 1 · 2 · ... · n，其中 0! = 1。int factorial(int n){    if (n == 0) {        return 1;                   // 基本情形    }    return n * factorial(n - 1);    // 递归情形}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

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

契约并非装饰：取 $n = -1$ 时，递归情形会以 $-2$ 调用，接着以 $-3$ 调用，永远到不了 0；而 $13!$ 放不进 int。许多入门教材用基本情形 if (n == 0 || n == 1) 来写这个阶乘，它多余但无害，而且对负数和结果的大小只字不提：它们的代码在 $n < 0$ 时不会终止，并从 $13!$ 起给出毫无意义的结果。这两个缺陷都将在各自的一节中考察。

基本情形与递归情形

每个递归函数都有一个或多个基本情形，它们被直接求解；还有一个或多个递归情形，它们以在某种确切意义上更小的实参调用同一个函数，并组合它返回的结果。

幂 $x^n$（$n$ 为自然数）由 $x^0 = 1$ 和 $x^n = x \cdot x^{n - 1}$ 定义：这里的规模是指数。自然数 $n$ 的各位数字之和（2026 的是 $2 + 0 + 2 + 6 = 10$）定义如下：若 $n < 10$，和就是 $n$，因为它只有一位数字；否则，它是 $\lfloor n / 10 \rfloor$ 的各位数字之和（这个数就是去掉最后一位数字的 $n$），再加上这最后一位数字 $n \bmod 10$。这里的规模是数字的位数。

#include <print>​// x 的 n 次幂。// 前置条件：n >= 0。// 后置条件：返回 x^n，其中 x^0 = 1。double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// n 的各位十进制数字之和。// 前置条件：n >= 0。// 后置条件：返回 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("2026 的各位数字之和：{}", digitSum(2026));}

2^10 = 10241.5^3 = 3.3752026 的各位数字之和：10

因此，写一个递归函数就是回答两个问题：哪些情形无须帮助就能解决，以及怎样由一个更小情形的解得到一个情形的解。如果两个回答都正确，函数就正确，下面一节将证明这一点。