P4745 递归求阶乘（入门）

解题思路

阶乘的意思：n! = 1×2×3×…×n。比如 5! = 1×2×3×4×5 = 120，6! = 1×2×3×4×5×6 = 720。

我们可以发现一个规律：n! = n × (n-1)!。比如 6! = 6 × 5!。这样求 n! 的问题，就可以变成求 (n-1)! 的问题，再变成求 (n-2)! 的问题……这就是递归的思想。

我们定义函数 fac(n) 返回 n! 的值。fac(n) = n * fac(n-1)。当 n 等于 0 或 1 时，n! = 1，这就是递归的出口，不用再往下递归了。

用例子验证：fac(6)=6×fac(5)=6×5×fac(4)=…=6×5×4×3×2×fac(1)=6×5×4×3×2×1=720，和样例一致。整个过程像一列火车：求第 6 节车厢，先求第 5 节，第 5 节又求第 4 节……一直问到第 1 节车厢（出口），再一节一节把答案带回来。

边界情况：题目保证 1≤n≤10，n 最大是 10，10! = 3628800，没有超过 int 能表示的范围，所以用 int 就行。递归最多 10 层，不会栈溢出。

注意：递归一定要有出口，否则会无限调用自己，导致程序崩溃。这道题的出口就是 n≤1 时返回 1。

参考代码

// 递归求阶乘：n! = n * (n-1)!
#include <iostream>

int fac(int n) {
    if (n <= 1) return 1;
    return n * fac(n - 1);
}

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

复杂度分析

从 n 一直递归到 1，一共要调用 n 次 fac，每次只做一次乘法和一次比较，所以时间复杂度是 O(n)。当 n=10 时只做 10 次运算，速度飞快。空间上递归深度是 n 层，占用 O(n) 的栈空间，n 只有 10，完全可以忽略。整个过程清晰简单，是学习递归的入门经典题目。