【什么是递归】递归是编程中一种常见的技术，指的是函数在定义中调用自身的过程。它通过将问题分解为更小的、相似的子问题来解决复杂的问题。递归通常用于处理具有重复结构的数据，如树形结构、列表、数字序列等。
一、递归的基本概念
| 项目 | 内容 |
| 定义 | 函数在执行过程中直接或间接调用自身 |
| 特点 | 需要有终止条件（基准情形） |
| 优点 | 代码简洁，逻辑清晰，适合处理嵌套结构 |
| 缺点 | 可能导致栈溢出，效率较低 |
| 应用场景 | 遍历树、计算阶乘、斐波那契数列、排序算法（如快速排序） |
二、递归的核心要素
1. 基准情形（Base Case）
递归必须有一个明确的终止条件，否则会无限循环下去。例如，在计算阶乘时，当 `n = 0` 或 `n = 1` 时，直接返回 1。
2. 递归调用（Recursive Step）
在每次调用中，问题规模应逐步缩小，直到达到基准情形。例如，计算 `factorial(n)` 时，调用 `factorial(n-1)`。
3. 分而治之（Divide and Conquer）
递归思想常与“分而治之”策略结合使用，即将大问题拆解为多个小问题，分别求解后再合并结果。
三、递归的优缺点对比
| 优点 | 缺点 |
| 代码简洁，易于理解 | 可能造成栈溢出 |
| 适合处理嵌套结构 | 执行效率可能较低 |
| 逻辑清晰，便于维护 | 调试困难，容易出现无限递归 |
四、递归与迭代的区别
| 比较项 | 递归 | 迭代 |
| 实现方式 | 函数调用自身 | 使用循环结构（如 for、while） |
| 内存消耗 | 每次调用都会占用栈空间 | 通常内存消耗较小 |
| 可读性 | 逻辑清晰，但易出错 | 代码结构简单，调试方便 |
| 适用场景 | 处理层次结构或树状数据 | 简单的顺序操作 |
五、常见递归应用示例
| 示例 | 描述 |
| 阶乘计算 | `factorial(n) = n factorial(n-1)` |
| 斐波那契数列 | `fib(n) = fib(n-1) + fib(n-2)` |
| 树的遍历 | 前序、中序、后序遍历 |
| 快速排序 | 分割数组并递归排序左右部分 |
六、如何避免无限递归
1. 确保有明确的基准情形
2. 每次递归调用都应使问题规模减小
3. 避免重复计算（可使用记忆化技术）
4. 合理设置最大递归深度（如 Python 中可通过 `sys.setrecursionlimit()` 调整）
七、总结
递归是一种强大的编程技巧，能够简化复杂问题的处理流程。但在使用时需注意其潜在的风险，如栈溢出和性能问题。合理设计递归函数，结合基准情形和合理的调用逻辑，才能充分发挥其优势。对于某些问题，也可以考虑用迭代方式替代递归，以提高效率和稳定性。
