P5739 【深基7.例7】计算阶乘——题解

解题思路

递归定义与阶乘定义完全一致：当 $n=1$ 时答案为 1；否则 $n!=n\times(n-1)!$。因为最大只到 $12!$，long long 足够。

正确性说明

递归终点正确返回 $1!=1$。假设函数能够正确得到 $(n-1)!$，那么返回 $n\times(n-1)!$，恰好等于 $n!$，因此对所有允许的 $n$ 都正确。

复杂度分析

时间复杂度 $O(n)$，递归栈空间 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
long long fact(int n){
    if(n==1) return 1;
    return 1LL*n*fact(n-1);
}
int main(){
    int n; cin>>n;
    cout<<fact(n)<<'\n';
    return 0;
}

#include <bits/stdc++.h> using namespace std; long long fact(int n){ if(n==1) return 1; return 1LLnfact(n-1); } int main(){ int n; cin>>n; cout<<fact(n)<<'\n'; return 0; }