【深基7.例7】计算阶乘

解题思路

使用递归：0! = 1，n! = n × (n-1)!。输入至多为 12。

正确性说明

基例返回 1 正确；若递归能求出 (n-1)!，乘 n 就是 n!，由归纳法得到结果。

易错点

递归必须有终止条件；不要把乘法写成加法。

复杂度

时间 O(n)，递归栈空间 O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

long long fact(int n) {
    return n <= 1 ? 1 : n * fact(n - 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    cout << fact(n) << "\n";
    return 0;
}