每个高效程序员都应该知道的递归高级概念

本文最初发表在 Towards Data Science 博客上，由InfoQ 中文站翻译并分享。

递归是最强大的编程方法之一。它在程序员工具箱中的有用工具清单上名列前茅，能够以令人震惊的少量代码解决极其复杂的问题。然而，递归通常是一个难以理解的概念，因为它需要从非标准的角度来看待命令是如何处理的。

本文将从简单的示例开始，逐步过渡到更具挑战性的示例，并附有大量图表：

• 递归的思维方式
• 递归关系
• 记忆化
• 分治法策略

递归是一种解决问题的方法，其中，函数在函数定义内调用自身。每个递归实现都需要有两个元素：

• 一个或多个 Base Case（边界条件、基准条件），它们是终止条件（Terminating Case），在这些条件中，不需要用更多的递归来进一步寻找答案。
• 一组规则（递归关系），通过启动另一轮递归，将其他条件减少到一个 Base Case。

例如，让我们考虑反向打印字符串。输入 “hello” 的输出应为 “olleh”。完成这一任务的贴袋方法是使用 for 循环，并打印出从最后一个索引到第一个索引的每个字符。

递归方法将首先创建一个函数 reverseString ，它接受一个字符串作为参数。如果输入的长度不为 0（则将作为 Base Case 或终止条件），我们将打印最后一个字母，并在当前字符串上启动另一个 reverseString 示例，但不包括最后一个字符串（因为它刚刚被打印）。

递归方法将首先创建一个函数 reverseString ，它接受一个字符串作为参数。如果输入的长度不为 0（则将作为 Base Case 或终止条件），我们将打印最后一个字母，并在当前字符串上启动另一个 reverseString 示例，但不包括最后一个字符串（因为它刚刚被打印）。

请注意，因为该函数是在其内部调用的，所以它自己创建了一个 for 循环。此外，在调用该函数的另一个实例之前必须存在 if 语句。否则，将抛出 RecursionError 或 RuntimeError 错误，因为脚本认为这个无线循环没有结束。这类似于 while True 无限循环。

让我们看看这个递归函数在 “hello” 上是如何起作用的：

在比较复杂的问题上进行递归是一件很困难的事情，因为确定它的两个组成部分——递归关系，即一个问题的结果与其子问题的结果之间的关系；在 Base Case 下，则是无需任何递归调用就可以直接计算的情况。有时，Base Case 又称为 Bottom Case，因为在这种情况下，问题已经缩小到最小的规模。

例如，杨辉三角形（Pascal’s triangle）中，其中每个数字都是它上面两个数字的和，三角形边上都有数字。如何使用递归来查找点 (i,j) 上任何值的值？递归关系的 Base/Terminatin Case 是什么？

递归关系可以用下面的公式来表示：

这在观察这个三角形的图时，是显而易见的。这个公式更好的地方在于，如果我们继续用这个公式把任意位置 (i,j) 分解为另外两个位置的和，那么就不可避免会导致 Base Case——1。杨辉三角形从 1 开始，从 1 的和开始，一个完整的复杂图案就出现了。

我们如何实现呢？

首先，让我们找到一组规则，确定何时满足 Base Case：单元格的值等于 1。注意，1 在两种情况下出现：要么位于第一列 (j=0) ，要么位于对角线 (i=j) 上。

现在实现起来很简单，如果满足 Base Case，则返回基值 (1)。否则，我们将继续减少问题，直到达到一个 Base Case，我们已经确定任何输入都将不可避免地被分解成 Base Case。

到现在为止，你应该已经领悟到递归之美了。在本文中，我们实际上用五行代码创建了一个自构造树（self-building tree）（如果你想缩短它，甚至也可以是三行代码）。当我们两次调用 pascal 函数时，启动了两个搜索分支，每个分支又启动另外两个，假设它们没有达到 Base Case。

递归是如何有效地工作的，这可能有点不可思议、令人困惑。让我们来通过一个例子来了解递归算法是如何运行的。

根据我们的递归关系，(4,2) 被分解成它上面的两个数 (3,1) 和 (3,2)。请注意，算法实际上并不知道这些单元格的值是 3，它所做的只是记录它们的位置。我们并不知道也不关心任何值，除非它能满足我们的 Base Case。根据我们的 Base Case (1)，我们可以计算其他非基准位置，但必须首先找到所有的 Base Case。

根据我们的递归关系，Case 被迭代分解，知道满足 Base Case（ j=0 或 i=j ）。由于我们知道这些 Base Case(1) 的值，因此可以根据 Base Case 填充其他值。

当然，这是递归算法如何工作的极其详细的视图，可能过于详细了。实际上，这三个步骤都不需要编程；它们是通过脚本自动执行的。就实现方面而言，你需要做的就是调用函数本身，并确保它在某些时候必须在 Base Case 下终止。

当我们调用 return pascal(i-1, j) + pascal(i-1, j-1) 时，我们不会把返回看作一个过程，而是将它当做一个数字。由于 pascal(i-1, j) 会启动自己的分支过程，但最终会返回另一个数字（比如 3），因此将它视为后者而非前者是有帮助的，这可能会导致不必要的复杂性和令人头疼的问题。

人们可能会倾向于指出这种递归算法中的一些低效之处。毕竟， “6” 被分解为 “3”，这两个 “3” 具有相同的分解（就值而言），但它被天真地计算了两次。这在递归中很常见，在递归中，一个 Case 的 Base Case 已经计算过，但会再次计算。为了解决这一问题，我们使用记忆化。

以斐波那契（Fibonacci）数列为例，其中前两个数字是 0 和 1，下一个数字是前面两个数字之和。根据之前的知识，我们知道 Base Case 是 0 和 1，我们的递归关系是 v(i) = v(i-2) + v(i-1) 。因此，我们可以构造一个简单的递归函数来查找 斐波那契数列在任意索引 i 处的值，从 0 开始。

请注意，虽然这是递归的一个巧妙应用，但效率极其低下。 “8” 被分解为 “3” 和 “5”，而 “5” 又被分解为 “3” 和 “2”。我们从头开始计算所有内容，并建立一个完整的搜索树，但其中有很多重复项。

使用记忆化，我们就可以通过创建缓存来解决这个问题。这可以通过使用字典来实现，并存储我们以前看到过的值。例如，当索引 6（值为 8）被分为索引 4 和索引 5（值分别为 3 和 5）时，我们就可以将索引 4 的值存储到缓存中。当索引 5 被计算为索引 3 加上索引 4 时，我们可以从缓存中提取索引 4，而不是通过构建另一棵树向下扩展到 Base Case 来重新计算索引 4。为了将记忆化添加到我们的功能中，我们添加了两个功能：首先，如果当前索引已存储在缓存中，我们只需返回存储的值；其次，在我们继续减少之前，应该将值添加到缓存中，以便可以加快进一步的操作。请注意，缓存必须是全局变量，或者不管命令调用的范围如何，都可以进行检索和更改该变量。

通过添加简单的记忆化，我们的递归函数比以前任何时候都快得多，功能也更强大得多。

递归是各种最快排序算法的核心。排序算法的目的是收集一个数字列表，然后从最小值到最大值返回它们。由于许多应用程序都依赖于快速排序，因此寻找一种能够对列表进行最快排序的算法非常有意义。一些最快的算法使用分治法策略的递归方法。

分治法是一种策略，在这个策略中，出事问题递归地分解为多个子问题。在每个子问题具有单位大小（类似于 Base Case）之后，将为每个子问题找到子解，然后再次递归地将这些子解组合在一起，形成一个完整的解。

例如，考虑快速排序（QuickSort）是排序中最快的算法之一，如果实现得当，它的执行速度可以比它的竞争对手和前身快 2~3 倍。快速排序从选择一个 “基准” （Pivot）开始。在简单的实现中，就我们的目的而言，基准的选择是任意的，但更专业的实现对所选的基准非常谨慎。

所有小于基准的元素移到基准的左侧，所有大于基准的元素移到其右侧。请注意，这个做操只是部分地解决了这个任务。

通过其基准分割列表的过程称为分区，因为基准将列表华为两个分区或边。每个分区在自身上调用另一个分区迭代，以此类推，直到一个分区达到一个 Base Case（1 个单元，简单地说，就是一个数字）。

在执行足够的递归后，原始列表将被分割得足够多，以至于不能再调用递归。在这一点，子解的组成只是将他们横向堆叠在一起。组成的结果是一个排序的列表。

请注意，快速排序遵循前面讨论过的许多递归构建块，只是在更高级别上。递归关系是组件的分区，Base Case 是大小为 1 的分区。从一个原始列表开始，递归调用相同的进程（选择基准、分区），直到结果只包含 Base Case。

关键点

• 递归是一种在函数内调用自身的编程方法，允许使用最少的代码进行循环和自动构建树。
• 在构造任何递归函数时，必须清楚地理解两个元素：递归关系和 Base Case。
• 记忆化是一种防止重复操作的方法，它将信息存储在缓存中，然后在需要时检索它们。
• 分治法是递归的许多更深层次的应用之一，它将问题递归地分解为若干子问题（Base Case），从这些子问题中可以很容易地提取和聚合子解，从而形成一个完整的解。

作者介绍：

Andre Ye，Critiq 联合创始人，机器学习、计算机科学和数学爱好者，Medium 编辑、最佳作家。

原文链接：

https://towardsdatascience.com/advanced-concepts-in-recursion-every-effective-programmer-should-know-de233a092dbf