C++ 阶乘

在数学中，正整数 n 的阶乘记作 n!，表示从 1 开始一直连续乘到 n 的乘积。例如 5 的阶乘就是 5! = 1 × 2 × 3 × 4 × 5 = 120。此外，数学上还特别规定：0 的阶乘等于 1（即 0! = 1），而负数没有阶乘。

在 C++ 中计算阶乘，常见的有 2 种实现方式：① 使用 for 循环依次累乘；② 使用递归函数层层求解。

使用 for 循环计算阶乘

使用 for 循环计算阶乘的思路非常直观：我们先准备一个保存乘积的变量 result，将它的初始值设为 1。接着让循环变量 i 从 1 依次递增到 n，每一轮都把当前的 i 乘到 result 上。

假如要计算 5 的阶乘，result 初值为 1，5 轮循环的累乘过程如下：

i = 1: result = 1 * 1 = 1
i = 2: result = 1 * 2 = 2
i = 3: result = 2 * 3 = 6
i = 4: result = 6 * 4 = 24
i = 5: result = 24 * 5 = 120

下面我们把这套累乘逻辑写成 factorial() 函数，并分别测试 0、5 和 10 的阶乘。

示例 1：循环累乘求阶乘

#include <iostream>

// 使用 for 循环计算阶乘
long long factorial(int n) {
    long long result = 1;    // 累乘初值设为 1
    for (int i = 1; i <= n; i++) {
        result *= i;         // 依次乘上当前的 i
    }
    return result;
}

int main() {
    std::cout << "0! = " << factorial(0) << '\n';
    std::cout << "5! = " << factorial(5) << '\n';
    std::cout << "10! = " << factorial(10) << '\n';
    return 0;
}

运行结果如下。

0! = 1
5! = 120
10! = 3628800

分析：

result *= i; 这句代码使用了复合赋值运算符，等价于 result = result * i;，表示在每一轮循环中把当前的 i 乘到 result 上。

当我们在 main() 中调用 factorial(0) 传入 0 时，循环条件 i <= 0 从一开始就不成立，for 循环体一次都不会执行。此时函数直接返回 result 的初始值 1，刚好符合数学上 0! = 1 的规定。

使用递归函数计算阶乘

除了使用循环，阶乘也是练习递归函数的经典例子。观察阶乘算式可以发现：5! = 5 × (1 × 2 × 3 × 4) = 5 × 4!。也就是说，想要算出 n 的阶乘，我们可以先求出 n - 1 的阶乘，再乘上 n。

按照这个递推规律，编写递归函数时需要明确以下 2 个部分：

• 终止条件：当 n <= 1 时（包含 0! 和 1!），不需要继续往下拆解，直接返回 1。
• 递推关系：当 n > 1 时，返回 n * factorial(n - 1)，把问题规模缩小一层继续调用自身。

下面我们使用递归函数来实现阶乘计算。

示例 2：递归求阶乘

#include <iostream>

// 使用递归函数计算阶乘
long long factorial(int n) {
    if (n <= 1) {
        return 1;    // 终止条件
    }
    return n * factorial(n - 1);
}

int main() {
    std::cout << "0! = " << factorial(0) << '\n';
    std::cout << "4! = " << factorial(4) << '\n';
    std::cout << "6! = " << factorial(6) << '\n';
    return 0;
}

运行结果如下。

0! = 1
4! = 24
6! = 720

分析：

在这个例子中，函数开头的 if (n <= 1) 是递归的终止条件。为什么这里写成 n <= 1 而不是 n == 1 呢？因为 0! 和 1! 的结果都是 1，写成 n <= 1 可以把这两种情况合并处理。

如果只写 n == 1，一旦调用 factorial(0)，程序就会跳过终止条件继续去求 factorial(-1)、factorial(-2)，最终陷入无限递归而导致栈溢出崩溃。

不妨看看调用 factorial(4) 时的执行过程，程序会先一层层向下拆解到终止条件：

factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1

当最内层的 factorial(1) 返回 1 后，程序再从下往上逐层代回算出乘积：先由 factorial(2) 算出 2 * 1 = 2，接着由 factorial(3) 算出 3 * 2 = 6，最后由 factorial(4) 算出 4 * 6 = 24 并返回。

对比上面两种写法，递归代码很贴近数学公式，但每一层函数调用都会占用额外的栈内存空间。而前面介绍的 for 循环写法从头乘到尾，没有函数调用开销，执行效率更高，因此在实际开发中我们更推荐使用循环写法。

阶乘的整数溢出问题

在前面的两个示例中，我们把函数的返回值和结果变量都声明成了 long long，而不是普通的 int。这是因为阶乘的数值增长得非常快，如果选择的数据类型取值范围不够大，很容易发生整数溢出。

常见整型能够准确表示的阶乘上限如下表所示。

如果直接使用 int 去计算 13!，代码在编译时并不会报错，但运行时会因为超出 int 上限而发生溢出，得出一个完全错误的数字。因此平时计算 20 以内的阶乘时，我们应该优先使用 long long（或无符号的 unsigned long long）来保存结果。

至于 50!、100! 这类超大阶乘，任何内置整数类型都装不下，需要借助数组或字符串按位模拟手工乘法。在初学阶段，小伙伴们先把 long long 范围内的阶乘写法掌握扎实就可以了。