Recursion

欢迎来到递归（Recursion）的世界！

在本章中，我们将探讨编程中最优雅且强大的概念之一：递归（Recursion）。起初你可能会觉得这有点“烧脑”，但别担心！我们会一步步拆解。当你读完这些笔记后，你会发现递归其实就是一种看待问题的新角度——透过将大问题拆解成较小且相同的子问题来解决。

想像一下俄罗斯套娃（Matryoshka）。为了拿到最中间的小娃娃，你必须先打开一个大娃娃，接着是稍微小一点的，再小一点的，直到最后找到那个不能再打开的最小娃娃为止。

1. 什么是递归？

在计算机科学中，当一个函数（function）在自己的程序代码中调用自己时，就会发生递归。这是一种解决问题的方法，其解决方案取决于相同问题在较小规模时的解法。

1.1 递归的基本特征（课程大纲 1.4.1）

每个成功的递归函数都必须具备这三个基本特征。若缺少它们，你的程序可能会死机或无限执行下去！

1. 基准情况（Base Case）： 这是“停止条件”。它是问题最简单的版本，可以直接得到答案，无需进一步递归。它能防止函数无限地自我调用。
2. 递归步骤（Recursive Step）： 这是函数自我调用的部分。它处理的是原始问题的一个稍微缩小的版本。
3. 迈向基准情况（Progress Toward the Base Case）： 每次函数调用自己时，它必须更接近基准情况（通常透过改变变量值来达成）。如果你没有向基准情况推进，就会产生无限递归（Infinite Recursion）。

快速复习盒：
记住 B.R.P. 口诀：
- Base Case (基准情况 - 停止)
- Recursive Step (递归步骤 - 重复)
- Progress (进度 - 逐步靠近终点)

2. 阅读与编写递归算法（课程大纲 1.4.2）

让我们看看经典范例：计算数字的阶乘（Factorial）。
\(n\) 的阶乘（记作 \(n!\)）是所有小于或等于 \(n\) 的正整数的乘积。
范例：\(4! = 4 \times 3 \times 2 \times 1 = 24\)

阶乘的递归定义：

- 若 \(n = 0\)，答案为 \(1\)（基准情况）
- 若 \(n > 0\)，答案为 \(n \times (n-1)!\)（递归步骤）

Python 实现：

def factorial(n):
    if n == 0: # 基准情况
        return 1
    else: # 递归步骤
        return n * factorial(n - 1) # 进度：(n - 1) 让我们更接近 0

你知道吗？ 如果你忘记写基准情况，电脑会不断地在内存中增加“层数”，直到耗尽内存空间。这就是所谓的堆栈溢出（Stack Overflow）！

3. 追踪递归：递归树（课程大纲 1.5.5）

当递归函数被调用时，电脑不会立即完成第一次调用。它会“暂停”目前的调用并开始一个新的。我们可以使用递归树（Recursion Tree）来可视化这个过程。

让我们追踪 factorial(3)：

1. 调用 factorial(3)。它需要 \(3 \times factorial(2)\)。（暂停！）
2. 调用 factorial(2)。它需要 \(2 \times factorial(1)\)。（暂停！）
3. 调用 factorial(1)。它需要 \(1 \times factorial(0)\)。（暂停！）
4. 到达基准情况： factorial(0) 回传 \(1\)。
5. 现在我们开始“解开”（Unwind）：
    - factorial(1) 变成 \(1 \times 1 = 1\)
    - factorial(2) 变成 \(2 \times 1 = 2\)
    - factorial(3) 变成 \(3 \times 2 = 6\)
最终答案：6

重点总结： 追踪过程能帮你理解“解开”的过程（将值一层层传回）是如何产生最终结果的。

4. 比较递归与迭代（课程大纲 1.4.3）

大多数可以用递归解决的问题，也可以用迭代（Iteration）（例如 for 或 while 循环）来解决。它们的比较如下：

4.1 递归

优点：
- 程序代码通常更短、更简洁、更优雅。
- 对于本质上是递归的问题（如树的遍历或“河内塔”问题）更容易求解。

缺点：
- 内存使用：较高。每次调用都会占用调用堆栈（Call Stack）的空间。
- 速度：通常较慢，因为多个函数调用会产生额外的负担（overhead）。

4.2 迭代

优点：
- 内存使用：较低。它重复使用相同的空间。
- 速度：通常较快，因为没有函数调用的额外负担。

缺点：
- 对于某些数学问题，程序代码可能会变得非常复杂且凌乱。

类比：
- 迭代就像是在跑道上跑圈。你处在同一个位置，只是重复同样的动作。
- 递归就像是走旋转楼梯。你虽然在做同样的圆周运动，但每次都处在不同的高度（层级）。

5. 常见的错误避坑指南

1. 丢失基准情况：这是最常见的错误！一定要问自己：“这什么时候会停止？”
2. 没有进度：如果你在 factorial(n) 内部调用 factorial(n)，\(n\) 的值永远不会变，你就永远无法到达基准情况。
3. 递归步骤逻辑错误：确保拆解问题的方式能导向正确的数学结果。

总结检查清单

- [ ] 我知道三个基本特征（基准情况、递归步骤、进度）吗？
- [ ] 我能在一段程序代码中识别出基准情况吗？
- [ ] 我能解释为什么递归比循环使用更多内存吗？
- [ ] 我能画出一棵简单的树来追踪递归函数吗？

如果一开始觉得很难，别担心！ 递归需要思维模式的转换。试着用笔和纸追踪一些小的范例；这是见证“魔法”发生的最好方法！