递归是一种特殊的编程技巧，函数通过调用自身来解决问题。
刚开始，这个想法可能感觉有点像魔法——或者有点奇怪——但一旦理解了，它就是一个非常强大的工具。

可以把它想象成面对面两面镜子反射。你看到一个倒影中又有倒影，层层叠叠……直到它最终渐渐消失。在递归中，这个“消失”非常关键——我们称之为基本情况，它是停止重复的原因。

递归的工作原理

一个递归函数:

1. 检查是否应该停止——这就是基本情况。
2. 如果没有停止，它会调用自身，但问题规模变得更小或更简单。

通过不断将问题拆解成更小的部分，递归能达到问题的最简版本，解决它，然后在所有调用返回时重建答案。

示例：阶乘计算

我们以阶乘为例。
在数学中，数字 n 的阶乘（写作 n!）表示：

n! = n × (n-1) × (n-2) × ... × 1

例如：

5! = 5 × 4 × 3 × 2 × 1 = 120

Python 中的递归版本如下：

def factorial(n):
    if n == 0:  # 基本情况
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 120

这里发生了什么：

• 如果 n 是 0，我们就达到了基本情况——根据定义，0! 等于 1。
• 否则，将 n 乘以 factorial(n - 1)（同一问题的一个较小版本）。
• 这个过程会一直重复，直到达到基本情况。

为什么使用递归？

递归可以：

• 对于结构自然重复的问题，非常优雅且简洁。
• 适合处理数学问题（阶乘、斐波那契数列）。
• 对于遍历树形结构数据（文件系统、家谱、游戏 AI 搜索）至关重要。

有时递归甚至可以替代循环，虽然它不一定是最高效的选项。

提示：将递归理解为“将问题分解为更小的自身问题，直到可以直接解决”为佳，通常更容易理解。

常见陷阱

重要！：一定要定义一个基本情况——否则函数会无限调用自身，直到 Python 抛出 RecursionError。

排错提示：

• “RecursionError: maximum recursion depth exceeded” → 你没有达到基本情况，或者基本情况定义错误。
• 如果递归感觉对问题来说过于复杂，可以尝试用循环代替。

递归刚开始时可能让人费解，但它只是让代码更智能、更具适应性的一种方式。 当你用几个问题练习过后，你会发现它不仅强大，还能使代码出人意料地简洁优雅。