1.递归是什么？

一、核心概念拆解

1. 本质：一种解决问题的方法，把复杂问题拆成结构相同、规模更小的子问题，直到问题小到可以直接解决。简而言之就是大事化小 小事化了 跟俄罗斯套娃一样。
2. 代码形式：在 C 语言中，就是函数内部直接或间接调用自己。

最简单的递归（错误的使用）

这是一段无终止条件的递归代码，它的执行过程是：

1. 调用main() → 打印hehe → 再次调用main() → 再打印hehe → 再调用main()... 无限循环。
2. 每一次main()调用都会在栈上创建新的栈帧，最终会因为栈空间耗尽，触发栈溢出错误（Stack Overflow）。

1.1 递归的思想

• 递（递推）：把大问题不断拆解成更小的同类子问题，直到触达终止条件（比如把 “求 5 的阶乘” 拆解为5×4!、4×3!… 一直拆到1! = 1）。
• 归（回归）：从最简单的子问题开始，把结果逐层向上返回，最终得到原问题的答案（从1! → 2! → 3! → … → 5!）

1.2 递归的限制条件

     递归两个必要条件

1. 必须有结束条件（出口）
2. 每次递归都要靠近结束条件

例如 阶乘的递归

例如 顺序打印一个整数的每一位

用递归的思想如果我们要顺序打印一个整数的每一位 那我们就把他拆成从个位 十位到百位等等

假如一个数字是1234 我们就可以把他拆成print（1234->print(123)+4->prin(12)+3+4

                                                                    ->print(1)+2+3+4   大事化小 

递归本质上是使用少量的代码执行了比较复杂的运算

递归与迭代

递归虽然能算出正确结果，但每次调用函数都要在栈区开辟一块叫「函数栈帧」的内存空间，保存局部变量等信息。

递归调用时，每一层递归都会占着自己的栈帧，直到递归结束、逐层返回才会释放。如果递归层次太深，会占用大量栈空间，甚至导致栈溢出（stack overflow）。

不想用递归的话，一般可以用 ** 循环（迭代）** 的方式来实现（这种方式不会使内存堆积导致栈溢出）

• 递归的优势是代码逻辑清晰、容易理解，很多问题天生就适合用递归的思路来描述；
• 迭代（循环）的优势是运行效率更高，没有函数调用的额外开销；
• 当问题特别复杂、用迭代写起来又臭又长时，递归的简洁性就可以抵消它的性能开销，让代码更易维护。

举例 斐波那契数列（前两个数的和为第三个数）

当我们输入一些较小的值的时候 很快的就能显示结果

可是当我们输入较大的值的时候呢？

这是vs输出不了吗？

不是的这是因为 我们使用递归占用的内存太大了 导致了栈溢出 这时候递归的缺点就表现出来了

所以我们采用迭代（循环）

速度非常快 效率高！！

• 迭代的优势：像斐波那契这类问题，用循环（迭代）实现，效率会比递归高出很多。
• 递归的正确使用态度：递归虽然写起来简洁，但会带来性能开销、栈溢出等问题，不要盲目迷恋递归，要根据场景选择。
• 递归的常见应用场景：在后续数据结构与算法学习中，递归主要用于这些场景：
  • 树 / 图的遍历（如二叉树前 / 中 / 后序遍历）
  • 分治算法（如归并排序、快速排序）
  • 回溯算法（如 N 皇后、排列组合问题）