P76049 递归阶乘 — 题解

专题： 函数
适用题目： 新生 OJ 本地题包中的 P76049，不要直接用于外站同名题。

解题思路

递归函数 fac(n) 在 n=0 时返回 1，否则返回 n*fac(n-1)。

复杂度

时间和栈空间均为 $O(n)$。

易错点

20! 超出 32 位，返回类型使用 unsigned long long。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

unsigned long long fac(int n){
    if(n==0)return 1ULL;
    return (unsigned long long)n*fac(n-1);
}
int main(void) {
    int n;scanf("%d",&n);printf("%llu\n",fac(n));return 0;
}

C++17 参考程序

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

unsigned long long fac(int n) {
    if (n == 0) return 1ULL;
    return (unsigned long long)n * fac(n - 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    cout << fac(n) << '\n';
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。