什么是递归

学习目标

本节先建立递归的基本概念。

学习完成后，你需要理解：递归不是一种神秘语法，而是一种问题表达方式。只要一个问题可以拆成规模更小、形式相同的问题，并且最终能到达一个明确的停止条件，就可以考虑用递归描述。

递归指的是一个函数在解决问题时，直接或间接调用自己。

但真正重要的不是“函数调用自己”这个动作，而是背后的思想：把一个大问题拆成更小的同类问题。

例如，要计算从 1 到 $n$ 的和，可以这样想：

sum(n) = sum(n - 1) + n

也就是说，想知道前 $n$ 个数的和，可以先知道前 $n - 1$ 个数的和，再加上 $n$ 。

这个表达中，sum(n) 和 sum(n - 1) 是同一类问题，只是规模变小了。这就是递归的核心特征。

递归不能无限调用自己，否则程序会一直向下执行，直到调用栈耗尽或程序崩溃。

因此，每个递归都必须包含停止条件，也叫递归出口。

对于求和问题：

sum(1) = 1
sum(n) = sum(n - 1) + n

当 $n = 1$ 时，答案可以直接得到，不需要继续递归。这个 sum(1) 就是递归出口。

如果没有递归出口，递归就像一条没有尽头的路。

判断一个问题能不能用递归时，可以先问两个问题：

第一个问题决定递归关系。第二个问题决定递归出口。

以阶乘为例：

factorial(n) = n * factorial(n - 1)
factorial(1) = 1

这里 factorial(n - 1) 是更小的同类问题，factorial(1) 是递归出口。

有些递归代码确实很短，但递归的价值不是“代码短”，而是“表达自然”。

例如树结构天然具有递归特征：一棵树可以由根节点和若干子树组成。处理一棵树时，常常就是先处理根节点，再递归处理子树。

这类问题如果用递归表达，思路会非常清晰。相反，如果强行用循环，有时需要手动维护栈或其他辅助结构。

递归和数学归纳有相似之处。

数学归纳通常包含两个部分：先证明最小情况成立，再证明如果较小规模成立，那么较大规模也成立。

递归也类似：先处理最小情况，再假设较小规模的问题能被正确解决，然后用它构造当前规模的答案。

这种思想会在后续分析递归函数正确性时非常有用。

递归是一种用更小的同类问题解决原问题的思考方式。

一个正确的递归通常需要两个部分：递归关系和递归出口。递归关系负责把问题规模变小，递归出口负责让递归最终停止。学习递归时，不要只盯着函数调用自己，而要关注问题是否具有可拆解的同类结构。