递归是什么：自己调用自己
递归是一种编程技巧，函数在执行过程中调用自身。就像俄罗斯套娃，打开一个娃娃，里面还有一个一模一样的娃娃。每次调用都是解决一个更小的相同问题，直到问题简单到可以直接解决。
两要素：出口 + 递推
递归必须有两个关键部分：出口（终止条件）和递推关系（如何缩小问题）。出口是递归停止的条件，比如“当数字为1时返回1”。递推关系把大问题拆成小问题，比如“n! = n × (n-1)!”。没有出口会导致无限递归。
调用栈：递下去与归回来
递归调用时，计算机会使用调用栈来管理函数调用。每次调用自身，就把当前状态压入栈顶（“递下去”）；当到达出口后，从栈顶依次弹出结果（“归回来”）。就像叠盘子，先叠上去，再一个个取下来。
递归 vs 迭代（循环）
| 对比项 | 递归 | 迭代（循环） |
|---|---|---|
| 实现方式 | 函数调用自身 | 使用循环结构 |
| 代码可读性 | 简洁，适合分治问题 | 直观，但复杂问题代码冗长 |
| 性能 | 有函数调用开销，可能栈溢出 | 通常更快，无额外开销 |
| 适用场景 | 树、图、分治算法 | 简单重复操作 |
常见坑：忘出口、栈溢出、重复计算
- 忘出口：没有终止条件，导致无限递归，程序崩溃。
- 栈溢出：递归层数太多，超出调用栈容量，比如计算大数的阶乘。
- 重复计算：相同子问题被多次求解，比如斐波那契数列的朴素递归，效率极低。可用记忆化或动态规划优化。