题意整理。

• 计算n的阶乘。
• 要求使用递归实现。

方法一（递归）

1.解题思路

递归的思路是，如果一个大问题可以拆分成若干个小问题，而这些小问题又可以拆分成若干个小问题，直到不能再拆分，并且直接可以得到问题的解，那么就可以用递归来实现。

• 递归终止条件：当n为1时，可以知道1的阶乘为1，递归终止。
• 递归如何推进：为了得到n的阶乘，我们可以通过n-1的阶乘变换而来。即$n!=(n-1)!\ast nn!=(n-1)!*n$。

图解展示：

2.代码实现

#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) {

    //当n为1时，递归终止
    if(n==1) return 1;
    //n乘以n-1的阶乘即可得到n的阶乘
    return n*factorial(n-1);

}

3.复杂度分析

• 时间复杂度：递归栈的深度为n，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：需要额外大小为n的递归栈，所以空间复杂度为$O(n)O(n)$。