一、什么是递归？¶

递归，简单来说就是“自己调用自己”。想象一下俄罗斯套娃：你有一个大套娃，里面装着一个更小的套娃，这个小套娃里又装着更小的，直到最小的套娃里没有其他套娃了。递归就像这样——一个问题被分解成更小的子问题，而每个子问题本身又是同一个问题的缩小版，直到子问题小到可以直接解决（不需要再分解），然后“反弹”回来得到最终结果。

二、递归的核心：终止条件 + 递归关系¶

递归有两个关键要素，缺一不可：
1. 终止条件：当问题小到不能再分解时，直接返回结果（避免无限循环）。
2. 递归关系：如何把大问题分解成更小的子问题，让每个子问题都用同样的规则解决。

三、用斐波那契数列学递归¶

斐波那契数列是递归的经典例子，它的定义很简单：
- 第 0 个数是 0（F(0) = 0）
- 第 1 个数是 1（F(1) = 1）
- 从第 2 个数开始，每个数等于前两个数之和（F(n) = F(n-1) + F(n-2)）

现在我们用递归思想来求第 n 个斐波那契数：

1. 定义递归函数¶

假设我们要写一个函数 fib(n)，返回第 n 个斐波那契数：

def fib(n):
    # 终止条件：n是0或1时，直接返回结果
    if n == 0:
        return 0
    if n == 1:
        return 1
    # 递归关系：大问题分解为小问题（调用自身）
    return fib(n-1) + fib(n-2)

2. 用例子拆解递归过程¶

以 fib(5) 为例，看看递归如何一步步计算：
- 求 fib(5) 需要先求 fib(4) 和 fib(3)；
- 求 fib(4) 需要先求 fib(3) 和 fib(2)；
- 求 fib(3) 需要先求 fib(2) 和 fib(1)；
- 求 fib(2) 需要先求 fib(1) 和 fib(0)；
- 当到 fib(1) 时，直接返回 1；到 fib(0) 时，直接返回 0。

逐层返回结果：
- fib(2) = fib(1) + fib(0) = 1 + 0 = 1
- fib(3) = fib(2) + fib(1) = 1 + 1 = 2
- fib(4) = fib(3) + fib(2) = 2 + 1 = 3
- fib(5) = fib(4) + fib(3) = 3 + 2 = 5

所以，第 5 个斐波那契数是 5。

四、递归的“套路”：层层嵌套，触底反弹¶

递归的过程就像“剥洋葱”：从最外层的问题开始，一层一层往里“挖”，直到挖到最内层的简单问题（终止条件），然后再一层一层返回结果。没有终止条件的递归会导致无限循环，比如忘记写 n==0 或 n==1 的情况，程序会一直调用下去直到崩溃。

五、递归的优缺点（简单提）¶

• 优点：逻辑清晰，容易理解和实现（比如斐波那契用递归几行代码就能解决）。
• 缺点：可能重复计算（比如 fib(5) 中 fib(3) 被计算了两次），效率较低。如果需要优化，可以用“记忆化递归”或“迭代”解决。

六、总结¶

递归的本质是“把大问题变小，小问题解决后再组合成大问题的结果”。用斐波那契数列做例子，我们看到了递归如何通过“终止条件+递归关系”实现自调用，最终得到答案。记住：递归的关键是别让它“越走越远”，要确保它能“回头”！

下次遇到需要分解成同类子问题的场景时，不妨试试递归的思路，也许会豁然开朗~