题目的主要信息：

• 一个整数$nn$n，求$nn$n的阶乘：$n\ast (n-1)\ast (n-2)\ast ...\ast 2\ast 1n*(n-1)*(n-2)*...*2*1$n∗(n−1)∗(n−2)∗...∗2∗1

方法一：递归

具体做法：

我们可以将求$nn$n的阶乘看成问题$f\left(n\right)=n\ast (n-1)\ast (n-2)\ast ...\ast 2\ast 1f(n)=n*(n-1)*(n-2)*...*2*1$f(n)=n∗(n−1)∗(n−2)∗...∗2∗1，而$f\left(n\right)=n\ast f(n-1)f(n)=n*f(n-1)$f(n)=n∗f(n−1)，这样我们就将$nn$n的问题化为了$n-1n-1$n−1的子问题，我们不断往前每次递归的$nn$n值乘上子问题的答案就可以了，直到$n=1n=1$n=1结束递归。

#include <iostream>
using namespace std;
long long recursion(int n){
    if(n == 1)
        return 1;
    return recursion(n - 1) * n; //递归计算n*f(n-1)
}

int main() {
	int n;
	cin >> n;
    long long factorial = recursion(n); //递归
	cout << factorial << endl;
	return 0;
}

复杂度分析：

• 时间复杂度：$O\left(n\right)O(n)$O(n)，一共递归$nn$n次
• 空间复杂度：$O\left(n\right)O(n)$O(n)，递归栈最大深度为$nn$n

方法二：迭代

具体做法：

除了自上而下的递归，我们也可以采用朴素的自下而上的累乘，遍历$22$2到$nn$n（$11$1就不用再乘了），将遇到的每个数累乘即可。

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	long long factorial = 1;
    for(int i = 2; i <= n; i++) //迭代2到n，1就不用了
        factorial *= i;  //累乘
	cout << factorial << endl;
	return 0;
}

复杂度分析：

• 时间复杂度：$O\left(n\right)O(n)$O(n)，一次遍历，一共循环$nn$n次
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间使用