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

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

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

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

• 递归的思维方式

• 递归关系

• 记忆化

• 分治法策略

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

• 一个或多个 Base Case（边界条件、基准条件），它们是终止条件（Terminating Case），在这些条件中，不需要用更多的递归来进一步寻找答案。

• 一组规则（递归关系），通过启动另一轮递归，将其他条件减少到一个 Base Case。

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

递归方法将首先创建一个函数 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