📘阶乘递归

📖概念讲解

【考点 · 3级】阶乘递归 —— 递归函数的经典入门题型，属于函数与递归类。

【说人话】递归就是函数自己调用自己。阶乘 n! 的定义天然是递归的：n! = n × (n-1)!，而 0! = 1 是递归出口（base case）。写递归记住两件事：① 找到终止条件，否则栈溢出；② 每次调用必须向终止条件靠近。阶乘递归是理解 DFS/BFS/动态规划的基础，3级必考！

💻代码示例

🧩互动小测

🏋️动手练一练

#include <iostream>
using namespace std;

long long factorial(int n) {
    if (n == 0) return 1;       // 递归出口
    return n * factorial(n - 1); // 递归调用
}

int main() {
    int n, k;
    cin >> n >> k;
    long long ans = factorial(n) / (factorial(k) * factorial(n - k));
    cout << "C(" << n << "," << k << ") = " << ans << endl;
    return 0;
}

📝易错点提醒

• 🚫 忘记写递归出口 → 无限递归，栈溢出（Runtime Error）
• 🚫 递归不向出口靠近 → 比如 factorial(n+1) 永远到不了 n==0
• 🚫 int 溢出 → 阶乘增长极快，13! 就超过 int 范围，必须用 long long
• 🚫 递归 vs 递推 → 阶乘可以用循环（递推）写，效率更高，但递归写法是理解后续 DFS/BFS 的基础