递归——工作原理、示例与基例

数学中的递归，是指用同一思想下更小的情形来定义一个函数、数列或过程。一个递归定义只有在包含基例，以及一条能让每个新情形朝基例推进的规则时，才能成立。

如果你只需要抓住核心概念，那就是：一旦“化为更小一步”的规则无法到达一个有效的停止点，递归就不再有意义。

数学中的递归是什么意思

递归定义不会把每一种情形都分别列出来。相反，它给出一个起点，以及一条由较小情形构造较大情形的规则。

这和直接公式不同。直接公式用一个表达式就能由输入得到答案。递归定义则是把问题一步步化简，直到到达一个已经已知的情形。

为什么必须有基例

基例就是停止点。没有基例，定义就会不断指向越来越小的情形，却永远无法结束。

基例还必须与你选择的规则相匹配。如果递归步骤是从 $n$ 化简到 $n-1$，那么对于你允许的输入，基例必须能按照这种模式被到达。

例题：阶乘的递归定义

阶乘是一个标准的递归定义。对于整数 $n \ge 0$，阶乘定义为

$$0! = 1$$

并且，当 $n \ge 1$ 时，

$$n! = n(n-1)!$$

这里，$0! = 1$ 是基例，而 $n! = n(n-1)!$ 是递归步骤。

要求 $4!$，就持续化简，直到出现基例：

$$4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!$$

现在应用基例 $0! = 1$：

$$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$$

这就是完整的递归模式：先化简到更小的情形，碰到基例，再一步步算回原来的问题。

递归与递推关系

递归是更广泛的概念。递推关系是数列中的一种递归规则，其中每一项依赖于前面的项。

例如，斐波那契数列就是由递推关系给出的，因为每一项都由前面的项定义。阶乘也是递归的，但它通常被表述为函数的递归定义，而不是数列的递推关系。

递归中的常见错误

漏掉基例

如果没有基例，这个定义就无法结束。

使用了不会变小的步骤

如果递归步骤没有朝基例推进，这个过程就可能无限循环，或者对某些输入变得无定义。

忘记规则的适用条件

在阶乘的例子中，规则 $n! = n(n-1)!$ 适用于 $n \ge 1$。这个条件很重要。没有它，你就可能在原本不打算定义的地方套用这条规则。

以为递归只是编程中的概念

递归在数学中早于代码而存在。它是一种通过引用更小情形来定义函数、数列和集合的方法。随后，人们常常用数学归纳法来证明这些递归定义的性质。

什么时候递归有用

当一个问题可以自然地拆分成它自身的更小版本时，递归就很有用。你会在阶乘、斐波那契型数列、递归定义的集合以及许多算法中看到它。

当较小情形与原问题具有相同结构时，递归尤其有帮助。如果较小情形其实并不是同一种问题，那么递归通常就不是合适的工具。

如何快速判断一个递归定义是否合理

问自己两个问题：

1. 我有基例吗？
2. 每一步递归都更接近基例吗？

如果有任意一个答案是否定的，这个定义就需要修改。

试试类似的问题

定义一个数列：

$$a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2$$

然后求出 $a_2$、$a_3$ 和 $a_4$。这是一个快速练习，帮助你在新情境中识别基例和递归步骤。