递归求阶乘

本节学会什么

• 将阶乘写成递归公式
• 为递归函数写出正确边界
• 对比递归与循环的适用场景

为什么需要它

阶乘的定义天然包含更小的阶乘：n! = n * (n - 1)!。它是练习“当前问题如何调用更小问题”和“哪里停止”的最小模型。

最小可运行示例

#include <iostream>

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

int main() {
    int n;
    std::cin >> n;
    std::cout << factorial(n) << '\n';
    return 0;
}

输入 4 时，调用链为 factorial(4) 到 factorial(0)，回到上层时依次得到 1、1、2、6、24。0! = 1 既符合数学定义，也是停止条件。

关键过程与易错点

• 只讨论 n >= 0。负数没有这里使用的阶乘定义，应由题目保证或单独判断。
• 13! 已超过 32 位 int 范围，示例使用 long long；题目范围更大时需要其他方法。
• 阶乘也可以用循环求。这个例子的目标是理解递归，不是说递归总是更快。
• 不要把边界写成 n == 1 却忘记输入 0 的情况。

动手检查

为 n = 0、1、5 写出预期结果，再运行程序核对。将递归调用前后的值临时输出，观察返回阶段的乘法顺序。

改写一个循环版阶乘，并用相同的输入比较两版结果。

立即练习