题目的主要信息：

• 编写一个函数 long long factorial(int n)，用于计算$nn$的阶乘
• 要求使用递归实现
• $nn$的范围是1-20

具体做法：

首先20的阶乘会超出int型的表示范围，因此题目用到了long long。

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

#include <iostream>
using namespace std;

long long factorial(int n);

int main() {

	int n;
	cin >> n;

	cout << factorial(n) << endl; //输出递归结果

	return 0;
}

long long factorial(int n) { //递归函数
    if(n == 1)
        return 1;
    return factorial(n - 1) * n; //递归计算n*f(n-1)
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一共递归$nn$次
• 空间复杂度：$O(n)O(n)$，需要直接到递归栈最深再往上乘（如图），因此递归栈最大深度也为$nn$