#创作计划#递归算法讲解
2025-08-19 20:01:08
发布于：广东
看完这篇帖子，能让你的递归从入门到入土！
递归是个好东西，每个人肯定都用过，但是有很多同学都不理解它的工作原理，还有很多高级的算法都会用到递归，怎么办呢？不要着急，今天我用保姆级讲解让你彻底搞懂递归。
字有点小？按Ctrl + 滚轮试试呢
1.递归的基本原理
递归的定义
递归是指在函数定义中，函数直接或间接地调用自身的过程。递归函数通常包含两个部分：基例和递归步骤。
基例（Base Case）
基例是递归的终止条件，当问题达到最简单的情况时，直接返回结果，避免无限递归。基例是递归的核心，没有基例会导致无限递归，最终导致栈溢出。
递归步骤（Recursive Step）
递归步骤将问题分解为更小的子问题，并调用自身解决这些子问题。递归步骤通过缩小问题规模，逐步接近基例。
你看得懂？厉害呀，反正我是一开始看不懂，
其实我觉得递归其实就是一个包含函数自身调用的函数(如果看不懂后面会讲，后面也是哦)，
它所说的基例确实就是递归的终止条件，最简单，基本的情况就是直接返回结果，它是递归必须写的东西，不然就会导致递归无限循环。
递归步骤就更简单了,它就是将问题分解为更小的（子）问题，并调用自身解决这些（子）问题，它的目的就是接近递归的终止条件，也就是接近你想让递归帮你解决的问题。
这时候要有聪明的小猪要问了，主播主播，举一个例子吧，我听不懂
那包可以的呀，那就举一个简单的例子吧，就阶乘吧（什么你连阶乘都不会，那你等会，我再去更一篇）
递归函数：
int factorial(int n) { //递归函数定义
if (n == 0) { // 基例(递归结束条件)
return 1; //结束递归
} else { //如果递归在这里不需要结束，那就继续接近递归结束条件
return n * factorial(n - 1); // 递归步骤（接近递归结束条件，也就是接近答案）
}
}
main()函数不写肯定不是懒
假设 n =5，代码执行流程如下（有点长，慢慢看哦）（不知道对不对）
调用factorial(5)：
检查n是否为0或1。5不等于0或1，进入递归步骤。
返回5 * factorial(4)。
调用factorial(4)：
检查n是否为0或1。4不等于0或1，进入递归步骤。
返回4 * factorial(3)。
调用factorial(3)：
检查n是否为0或1。3不等于0或1，进入递归步骤。
返回3 * factorial(2)。
调用factorial(2)：
检查n是否为0或1。2不等于0或1，进入递归步骤。
返回2 * factorial(1)。
调用factorial(1)：
检查n是否为0或1。1等于1，满足基例条件。
返回1。
回溯计算：
factorial(1)返回1。
factorial(2)计算为2 * 1 = 2，返回2。
factorial(3)计算为3 * 2 = 6，返回6。
factorial(4)计算为4 * 6 = 24，返回24。
factorial(5)计算为5 * 24 = 120，返回120。
输出结果：
main函数输出5! = 120。
例子举完了，如果还不懂，那你有两个选择：
1.私信问我
2.自己把自己放在烤架上烤了
ok,那我们再来总结一下
递归的实现结构
递归函数的典型结构如下：
返回类型 函数名(参数列表) {
if (满足基例条件) {
返回基例的结果;
} else {
处理递归步骤，调用自身并返回结果;
}
}
好的，看到这里递归的理论知识已经快讲完了，最后，让我们来拓展一个知识点：
递归的优缺点
优点：
代码简洁：递归能够用非常简洁的代码实现复杂的问题。
直观性强：对于某些问题（如树的遍历、分而治之的问题），递归的思路更直观。
减少重复代码：递归能够避免在循环中重复处理相同的问题。
缺点：
效率问题：递归函数通常会进行大量的重复计算，导致效率较低。
栈溢出风险：递归深度过大时，可能会导致栈溢出，从而程序崩溃。
内存开销：每次递归调用都会在栈中保存函数的状态，这会增加内存的使用。
好了，恭喜你，递归的基础理论知识已经掌握了。俗话说：”实践出真知“，那就来吧
首先，我们要了解递归的应用场景
递归在以下场景中非常有用：
1.树和图的遍历：例如，二叉树的前序遍历、中序遍历、后序遍历。
2.分而治之的问题：例如，归并排序、快速排序。
3.回溯算法：例如，解决八皇后问题、迷宫问题。
4.数学问题：例如，计算阶乘、幂函数、斐波那契数列等。
其次，举几个例子(开始做题)
做题模式：看题解思路（不看最好）+自己写代码
题目（不看题解思路）：【递归】斐波那契数列
题目+题解：【递归】斐波那契数列题解
今‘天’写不完了，出‘于’后再写
..........................................
..........................................
..........................................
全部评论 4
实际上函数里不用写 else
int func(int n) { if (n == 1) return 1; return func(n - 1) * n; }这样就可以了（因为 return 以后就相当于函数完成了）
1周前 来自 上海
0
有帮助，赞一个