在 C++ 中计算数字的阶乘

在 C++ 中，对于非负整数，可将从 2 到 n 的各个因子相乘来计算 n!。通常，迭代循环是最简单的做法；递归则更直接地体现了阶乘的数学定义。下面的示例展示这两种方法，并说明 unsigned long long 的取值限制。

阶乘的定义与输入

对于非负整数 n，阶乘 n! 是从 1 到 n 的所有正整数的乘积。按照定义，0! 等于 1；即使没有因子可相乘，这一定义也能让涉及阶乘的公式保持一致。例如，5! 表示 5 * 4 * 3 * 2 * 1。

下面的示例用于计算非负整数的阶乘。阶乘常用于排列、组合和概率计算。阶乘值增长很快，因此输入有效并不意味着结果一定能由某种 C++ 整数类型表示。

使用迭代法计算阶乘

迭代法会保存一个累积乘积，并将从 2 到 n 的每个整数依次乘进去。将乘积初值设为 1，就能同时正确处理 0 和 1：循环不会执行，初始值本身就是结果。

运行此示例：

本节中的代码以及显示的标签或输出仍为英文。

#include <iostream>

unsigned long long factorial(unsigned int n) {
  unsigned long long result = 1;
  for (unsigned int factor = 2; factor <= n; ++factor) {
    result *= factor;
    if (factor == n) {
      break;
    }
  }
  return result;
}

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

5! = 120

累加器 result 保存当前乘积。每轮循环都会乘入下一个因子。当 factor 达到 n 时，break 会在循环递增之前退出，从而避免无符号计数器达到最大值时发生回绕。若 n 为 0 或 1，循环不会执行，结果保持初值 1。此实现使用固定数量的调用栈空间。

使用递归法计算阶乘

递归表达了恒等式 n! = n * (n - 1)!。当 n 为 0 或 1 时，基例返回 1；其他每次调用都会使用更小的参数，因此最终会到达基例。

本节中的代码以及显示的标签或输出仍为英文。

#include <iostream>

unsigned long long factorial(unsigned int n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

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

5! = 120

这个函数容易与阶乘的数学定义对应起来，但每向基例推进一步都会产生一次函数调用。递归较深时会占用更多调用栈空间。参数是无符号类型，因此该函数不接受负数；如果调用方收到的是有符号输入，应先检查其值，再转换为无符号类型。提供的运行记录显示，此示例输出 5! = 120。

处理输入限制与整数溢出

这里将阶乘定义为适用于非负整数。有符号输入传给接受 unsigned int 的函数之前应先检查；负数转换为无符号类型后会变成一个较大的正数。

两个示例都使用 unsigned long long。C++ 保证该类型至少能表示到 20!，但它无法表示所有阶乘。当乘法结果超出类型的最大值时，无符号算术会按比该最大值大 1 的数取模回绕。回绕后的值并不是数学意义上的阶乘。对于更大的输入，可以使用大整数库；也可以在每次乘法之前检查 result <= max / factor，其中 max 为 std::numeric_limits<unsigned long long>::max()。

选择一种方法

如果要直接计算并保持调用栈用量固定，可以使用迭代法。如果递归与阶乘定义的直接对应关系能让周围的算法更易理解，也可以使用递归法，但输入应足够小，以适应可用的调用栈。无论采用哪种方法，都应根据应用所需的最大结果选择数值表示方式，并明确处理输入范围和溢出限制。阶乘示例适用于组合数学和概率计算；当数值超出内置整数范围时，实际应用通常可以通过代数化简或使用大整数类型来处理。