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

    // write your code here......
    if(n==1){
        return 1;
    }
    return n * factorial(n-1);
}

递归 (C++ 零基础彻底讲透，结合你的数组基础)

你之前问的数组、指针、string都是C++语法层面的知识，而递归是「编程算法思想」+「函数调用语法」的结合体，也是C++里非常核心的知识点，理解起来有一点点绕，但我用「大白话+你熟悉的数组案例」讲，保证你彻底懂，没有晦涩概念！

✅ 一、递归的「大白话定义」（最易懂，先记这个）

递归 = 函数自己调用自己

一个递归函数，就是在函数的函数体内部，直接或间接的调用了函数本身。

可以用2个生活比喻帮你理解，瞬间通透：

递归像「剥洋葱」：想剥到洋葱芯，必须先剥掉外面一层，再剥里面一层，一层一层剥，直到剥到芯（停止），本质就是「做同一件事，每次范围变小」；
递归像「套娃」：打开一个套娃，里面还有一个一模一样的套娃，再打开，还有更小的，直到打开最里面那个空的（停止），本质就是「重复做同一个动作，直到满足停止条件」。

举个最简单的C++递归代码（一眼看懂形式）

#include <iostream>
using namespace std;

// 这就是一个递归函数：函数内部调用了自己
void func() {
    cout << "我是递归函数" << endl;
    func(); // 核心：自己调用自己
}

int main() {
    func();
    return 0;
}

这个代码运行后会无限打印文字，直到程序崩溃——这是「无终止的递归」，也是新手最容易写的错误递归，后面会重点说为什么错。

✅ 二、递归的「专业定义」（补充理解）

从解决问题的角度，递归的本质是：

把一个「大问题」，拆解成「和原问题一模一样、但规模更小的子问题」，不断拆解，直到子问题小到能「直接得出答案」，再通过子问题的答案，一步步回推得到原问题的答案。

举个数学例子（所有人学递归的第一个案例）：求自然数的阶乘：n! = n × (n-1) × (n-2) × ... × 1

大问题：求 5!
拆成小问题：5! = 5 × 4!
再拆：4! =4 ×3!、3! =3×2!、2! =2×1!
最小问题（能直接答）：1! = 1
回推答案：2!=2×1 →3!=3×2 →4!=4×6 →5!=5×24=120

这就是递归解决问题的完整逻辑，所有递归都是这个套路。

✅ 三、【重中之重】递归的「两个绝对必要条件」（缺一必死！99%新手踩坑）

你刚才看到的无限打印的递归函数，为什么会崩溃？因为它缺少了递归的核心约束。

C++中，一个能正常运行、不出错的递归函数，必须同时满足「两个条件」，少一个都不行！

✔ 条件1：必须有「递归出口」（终止条件 / base case）

含义：递归不能无限调用自己，必须在满足某个条件时，停止调用自己，直接返回一个确定的结果。
作用：防止「死递归」，这是递归的生命线。
比如阶乘的递归出口：n == 1 时，返回 1

✔ 条件2：必须有「递推公式」（递归关系 / 缩小问题规模）

含义：每次递归调用自己时，必须让「问题的规模变小」，也就是传入的参数要发生变化，让问题一步步靠近「递归出口」。
作用：保证递归能最终走到出口，而不是原地打转。
比如阶乘的递推公式：n! = n × (n-1)!

✅ 四、第一个完整的「合法递归函数」- 阶乘计算（带注释，能直接运行）

结合上面的两个条件，写第一个能正常运行的递归代码，这是你必须掌握的入门案例：

#include <iostream>
using namespace std;

// 递归求n的阶乘：满足两个必要条件
int fact(int n) {
    // 条件1：递归出口（终止条件）- 问题最小化，直接返回答案
    if(n == 1) {
        return 1;
    }
    // 条件2：递推公式 - 大问题拆小问题，规模变小(n→n-1)，调用自己
    return n * fact(n-1);
}

int main() {
    int res = fact(5);
    cout << "5! = " << res << endl; // 输出：5! = 120
    return 0;
}

✅ 关键：带你走一遍递归的执行流程（先「递」后「归」，核心理解点）

递归的执行过程，永远是 「先递下去，再归回来」，这四个字是递归的灵魂，一定要记住！fact(5) 的完整执行步骤：

递下去（拆解问题，调用自己）：fact(5) → 需要计算 5 * fact(4)fact(4) → 需要计算 4 * fact(3)fact(3) → 需要计算 3 * fact(2)fact(2) → 需要计算 2 * fact(1)fact(1) → 触发出口，直接返回 1 （递的过程结束）
归回来（计算结果，回推答案）：fact(2) = 2 * 1 = 2 → 返给fact(3)fact(3) = 3 * 2 = 6 → 返给fact(4)fact(4) = 4 * 6 = 24 → 返给fact(5)fact(5) = 5 * 24 = 120 → 最终结果

小技巧：递归的执行顺序不用死记，记住「先递到出口，再往回算」就行，所有递归都是这个流程。

✅ 五、结合你的「数组知识」，写数组相关的递归（最贴合你的学习进度，必看）

你之前一直在学数组、指针，这里给你两个数组相关的递归案例，完美衔接你之前的知识点，也是面试高频题，比阶乘更实用！

案例1：递归求「数组的累加和」（数组传参+递归结合）

你知道数组传参后会退化成指针，这里正好用上，逻辑非常简单：

大问题：求数组arr[0~n-1]的和递推公式：sum(arr, n) = arr[0] + sum(arr+1, n-1) （首元素 + 剩余数组的和，规模变小）递归出口：n == 0 时，数组为空，和为0

#include <iostream>
using namespace std;

// 递归求数组累加和，arr是退化后的指针，n是数组元素个数
int getArrSum(int arr[], int n) {
    // 条件1：递归出口 - 数组无元素，和为0
    if(n == 0) {
        return 0;
    }
    // 条件2：递推公式 - 首元素 + 剩余数组的和，规模n→n-1
    return arr[0] + getArrSum(arr+1, n-1);
}

int main() {
    int arr[4] = {1,2,3,4}; // 你熟悉的数组arr[4]
    int sum = getArrSum(arr, 4);
    cout << "数组和 = " << sum << endl; // 输出：10
    return 0;
}

案例2：递归遍历「数组的所有元素」

不用for循环，用递归遍历数组，逻辑和上面一致，也是数组退化指针的经典用法：

#include <iostream>
using namespace std;

void printArr(int arr[], int n) {
    if(n == 0) { // 出口：无元素，停止打印
        return;
    }
    cout << arr[0] << " "; // 打印当前首元素
    printArr(arr+1, n-1);  // 递归遍历剩余数组
}

int main() {
    int arr[4] = {1,2,3,4};
    printArr(arr,4); // 输出：1 2 3 4
    return 0;
}

✅ 六、递归的「底层运行原理」（为什么能自己调用自己？和栈有关）

这个知识点帮你理解「递归的本质」，不用死记，知道原理就行，也是C++的基础知识点：

递归函数的调用，是基于「函数调用栈」实现的。

C++程序运行时，会有一块专门的内存空间叫「栈」，每次调用函数（不管是普通函数还是递归函数），都会在栈上为这个函数创建一个「栈帧」（存储函数的参数、局部变量、返回地址）。

递归的运行过程，就是不断在栈上创建新的栈帧（递下去），直到触发递归出口，然后从栈顶开始销毁栈帧，同时计算返回值（归回来），直到栈空。

❗ 递归的致命坑：栈溢出（Stack Overflow）

你之前看到的「无终止递归」，会不断创建栈帧，栈的内存空间是有限的，最终栈会被占满，程序直接崩溃，这个错误叫「栈溢出」。即使是合法的递归，如果递归层数太多（比如求 fact(10000)），也会栈溢出！这是递归的天然缺陷，后面会说解决方案。

✅ 七、递归的「优缺点」（什么时候用？什么时候不用？）

学完递归，一定要知道它的适用场景，不能无脑用，结合你的学习阶段，总结最核心的优缺点，都是考点：

✔ 递归的优点（为什么要学递归？）

代码极度简洁，逻辑清晰：解决同一个问题，递归代码往往比循环代码短很多，比如数组求和，递归只用3行核心代码，循环需要写for循环+累加变量。
解决特定问题「事半功倍」：有些问题天生适合递归，用循环写会非常复杂，甚至写不出来，比如：二叉树遍历、快速排序、归并排序、斐波那契数列、汉诺塔问题。
锻炼「分治思想」：递归是「分而治之」算法思想的核心体现，学递归就是学算法思维，对后续学习数据结构（树、图）至关重要。

✔ 递归的缺点（为什么有时不用递归？）

效率较低，有额外开销：每次递归调用都要创建栈帧，栈帧的创建和销毁都需要消耗内存和CPU，效率比循环低。
有栈溢出风险：递归层数太多，必然栈溢出，程序崩溃。
可读性对新手不友好：递归的逻辑是「逆向」的，新手刚开始看递归代码会觉得绕，需要多写多练才能适应。

✅ 八、递归和循环的关系（重要结论）

✅ 所有能用递归解决的问题，都能转换成循环解决！反之不一定。

递归是「用空间换时间」（栈空间换代码简洁），循环是「用时间换空间」（无栈开销，但代码可能复杂）。比如阶乘的循环写法：

int fact(int n) {
    int res =1;
    for(int i=2;i<=n;i++){
        res *=i;
    }
    return res;
}

两种写法都能解决问题，在学习阶段，建议先用递归写，理解逻辑，再用循环改写，加深理解。

✅ 九、新手写递归的「万能步骤」（按这个写，永远不会错！）

这是我总结的新手写递归的黄金法则，按步骤写，所有递归题都能迎刃而解，从入门到精通都适用，一定要记下来：

写递归的3个步骤（固定顺序，不能乱）

第一步：先确定「递归出口」 → 先想：问题最小化到什么程度能直接出答案？
第二步：再确定「递推公式」 → 再想：大问题怎么拆成规模更小的同类型子问题？
第三步：写代码实现 → 把出口和公式翻译成代码，调用自己即可。

举例：求数组和，先写出口 n==0 return 0，再写公式 arr[0]+sum(arr+1,n-1)，代码就出来了，无脑套用！

✅ 总结（所有知识点浓缩，建议收藏，新手必背）

递归是C++的「分水岭」知识点，也是算法的基础，把下面的核心点记牢，你就彻底掌握了递归：

递归的本质：函数自己调用自己，解决问题的思路是「大事化小，分而治之」；
递归的两个必要条件：递归出口（终止） + 递推公式（缩小规模），缺一不可；
递归的执行流程：先递下去，再归回来，基于函数调用栈运行；
递归的核心优点：代码简洁、逻辑清晰；核心缺点：效率低、栈溢出风险；
新手写递归的万能步骤：先写出口 → 再写公式 → 最后写代码；
递归和循环的关系：递归能转循环，循环不一定能转递归。

递归的理解需要「多写多练」，刚开始写会觉得绕，但写3-5个案例后，你会发现递归其实非常简单，而且会爱上这种简洁的写法！✨

题解 | 递归的实现 | 函数实现计算一个数的阶乘