使用递归 | 纱雾の闺房

前言

您可能熟悉『递归』的概念，这是根据自身定义函数的方式。就像要步行到达某个地方，您需要检查前面的步数是否为非零，如果这样做，您必须迈出一步，然后将相同的过程应用于新的方式。

第1部分 - 我应该如何使用递归？

请记住：在函数式编程中，我们避免将变量视为某些具有可变状态的存储单元。遵循这个限制，我们应该避免循环^[1]——为了检查是否应该停止循环，我们应该有一个某种类型的计数器，且它的状态在我们进行迭代步骤时不断变化。根据您的经验，避免循环似乎是一个思想问题，一个难以达成或一个完全疯狂的想法。让我们讨论递归如何作为循环的替代方案，为什么您绝对不想在 Python 中执行它，以及为什么在某些情况下甚至想在 Python 中执行它。

考虑两个非常常见的列表（list）函数的迭代实现：

def sum(list):
    res = 0
    for x in list:
        res += x
    return res


def length(list):
    res = 0
    for x in list:
        res += 1
    return res

让我们试着根据这些概念来定义列表『求和』和『长度』。首先请记住，在构建递归算法时，您应该清楚地定义递归边界和递归逻辑，以便您可以将原始问题细化为规模更小的同源问题。在多次细化后，必然会遇到一种不可细分的『原子问题』，即上文提到的递归边界。在上面给出的示例中，边界状态显然没有什么需要做的，并且每次递归转换都会缩小问题规模。现在，诸如sum()或length()之类的列表函数的边缘情况是什么？显然，这是空列表（即[]）的情况。在这种情况下，我们将这两个都定义为零。现在，我们如何将任务减少到相同但更小的任务？显然，我们应该缩短我们的列表。所以我们需要对列表的一部分做一些事情，然后省略处理过的部分，记住它对结果的贡献，并以同样的方式处理没有这部分的列表，直到我们省略下一部分后得到的列表是一个空列表。

def head(list):
    return list[0]


def tail(list):
    return list[1:]


def fsum(list):
    return 0 if not list else head(list) + fsum(tail(list))


def flength(list):
    return 0 if not list else 1 + flength(tail(list))


print(fsum([2, 3, 5]), flength([2, 3, 5]))

>>> 10 3

在这里，我们定义了返回列表第一个元素的head()函数——这是我们单独做一些事情的部分，以便稍后省略它并获得更短的列表；这个较短的列表是tail()函数返回的内容——除了列表首元素剩下的一切。因此，在求和的情况下，如果一个列表非空，我们将其第一个元素的值和所有其他元素的总和相加；如果它是空的，我们简单地返回 $0$ 作为它的总和。显然，通过这种方式，我们将列表的第一个元素一个一个地分解，并将它们插入到末尾带有 $+ 0$ 的加法链中。在计算长度的情况下，它甚至更容易，因为某些特定列表的长度基本上与该列表的所有元素都更改为 $1$ 的总和相同。

这是处理列表的通用模式，还有很多函数可以用这种递归方式定义：我们需要定义列表函数、头部函数、粘合函数和初始值。listFunc()函数是我们要计算的函数，headFunc()函数是每个单独元素对结果值的贡献方式，glue()函数是我们定义计算结果^[2]的方式，init初始状态是一个空列表。

listFunc = init if list.isEmpty() else glue(headFunc(head), listFunc(tail))

当然，这种模式并不涵盖所有情况。如果我们愿意，我们可以用递归调用链模拟显式循环。只是我们没有使用可变状态的计数器，而是在每次递归调用时传递它的更新值。

def fsum2(list):
    def helper(n, acc, list):
        return acc if n < 0 else helper(n - 1, acc + list[n], list)

    return helper(len(list) - 1, 0, list)


print(fsum2([2, 3, 5]))
>>> 10

就像在这个函数中一样：我们定义了一个内部迭代模拟函数作为辅助，它有一个跟踪计数器和累加器来计算结果。该过程从将计数器设置为列表长度减一并将累加器设置为零开始，然后在每次调用时，我们通过相同的函数传递 $n$ 的递减值和增加的第 $n$ 个元素的值的累加值。通过这样做，我们将遇到 $n < 0 - 1$ 的情况，这意味着我们已经处理了整个列表并且累加器存储了所有元素的总和，因此我们返回了累加总和。

第2部分 - 有异议！

除了那些迭代非常复杂的算法^[3]，不幸的是，这种递归写法在 Python 中的效果非常糟糕。你看，每次我们进行函数调用时，程序的求值应该暂停、函数调用位置和此时的程序状态被保存，随后函数完成求值并将结果返回。也就是说，每次我们进行函数调用时，都会分配一定数量的内存。如果我们进行了大量调用，并且递归方法假设我们进行了大量调用，则会花费大量内存。好消息是：有一个称为 尾递归 Tail Recursion 优化的功能。看看我们定义的这些递归函数：如您所见，递归调用是我们在函数体内做的最后一件事。在大多数假定函数式编程可能性的语言^[4]中，如果您以这种方式编写递归函数，它们实际上不需要为每次调用额外空间：编译器足够聪明，可以理解这种模式并将必要的数据以更紧凑的方式存储。坏消息是：Python 不支持尾递归优化，这就是为什么大多数时候您会更喜欢循环或其他替代方法的原因。除此之外，Python 对最大递归深度也有限制^[5]。如果我没记错的话，如果嵌套调用的数量超过一千，它就会停止程序^[6]。不过，如果需要，这个限制很容易克服^[7]。

第3部分 - 总之，我为什么要使用递归？

不过，如果对这些一般的任务使用递归是一个坏主意，那么有时它工作得非常好。即使在 Python 中，您也希望它胜过其他一切。

首先，递归有时是一个简短且简单的解决方案，而相同功能的迭代算法复杂得难以实现。例如，在另一课中提到的快速排序算法使用了递归的思想，即使在迭代实现的情况下，如果你试图避免它，事情只会变得更糟。

另一个经典例子是汉诺塔问题^[8]。你有三根柱子，有许多不同直径的环叠在柱子上形成一个金字塔，任务是按此顺序将所有的环移动到另一根柱子上（无所谓哪一根空柱子），但有以下限制：您一次只能移动一个环，且不能将大环叠在小环上。

汉诺塔示意图

甚至在您弄清楚如何解决这个问题之前，您就可以通过将其减少到自身的较小版本来制定解决任务的递归过程。

假设我们在 A 杆上有 $n$ 个环。我们如何将其移动到 C 杆？那么根据规则，我们需要以某种方式将除了最底部最后一个环之外的所有环（即顶部 $n - 1$ 个环）移动到B杆，然后把这个环从 A 杆移动到 C 杆，然后将这顶部的 $n - 1$ 个环再次从 B 杆移动到 C 杆。

这很明显，但是我们如何将 $n - 1$ 个环移动到 B 杆上？实际上以完全相同的方式即可，要将 $n - 1$ 个环移至 B 杆，我们需要将顶部 $n - 2$ 个环移至C杆，将底部第 $n - 1$ 个环移至 B 杆，然后再将 $n - 2$ 个环移动至 B 杆。我们如何将 $n - 2$ 个环移动到 C 杆上？再一次，将顶部 $n - 3$ 个环移动到 B 杆，依此类推。这样我们会逐步减少要移动的环数，直到 $n = 0$ 。

如果 $n = 0$ ，则意味着在下一步或上一步中，我们需要移动的环是唯一需要移动的，因此其顶部没有别的环，不需要继续细化任务。

所以，原理很简单：要将 $n$ 个环从初始杆移动到目标杆，我们需要将 $n - 1$ 个环移动到唯一剩下的杆（我们称其为过渡杆），然后将一个环从初始杆移动到目标杆，最后从过渡杆移动 $n - 1$ 个环到目标杆。如果 $n = 0$ ，我们什么都不做。为了编写程序，最后要做的一件事是弄清楚如何根据初始杆和目标杆的编号确定过渡杆的编号。此处我们有3根杆子，其编号总和为 $1 + 2 + 3 = 6$ ，初始杆编号为 $s$ ，目标杆编号为 $t$ ，那么过渡杆的编号 $u = 6 - (s + t)$ 。

这是一种可行的实现：

def hanoi(amount, source, target):
    if amount:
        hanoi(amount - 1, source, 6 - (source + target))
        print(source, '->', target)
        hanoi(amount - 1, 6 - (source + target), target)


n = int(input('环的数量：'))
>>> 环的数量：3

hanoi(n, 1, 3)
>>> 1 -> 3
..| 1 -> 2
..| 3 -> 2
..| 1 -> 3
..| 2 -> 1
..| 2 -> 3
..| 1 -> 3

让我们用几个环进行测试，由它打印出一系列要执行的动作。您可以自己检查它，但它实际上会打印出一系列导致所需结果的有效移动。不仅如此，这个顺序是最佳的，因为在这个过程中没有低效的地方。为了移动 $n$ 个环，我们真的需要先移动 $n - 1$ 个环，然后是最底部的那个，最后又是它上面的 $n - 1$ 个环。没有办法绕过这个事实——我们制定了解题的充要条件。

还有另一种问题，它不仅是递归运行良好的情况，而且也是对递归过程的结构给出直观直观的好方法。有一个分形的数学概念，自相似分形尤其著名。粗略地说，二维自相似分形是一类几何图形，它由与自身相似且更小的图形组成。例如，下图称为谢尔宾斯基三角形，如您所见，它具有递归结构（根据自身定义），每个大三角形由3个较小^[9]的相似三角形组成。

谢尔宾斯基三角形

让我们使用 Python 的turtle模块绘制它。很明显，我们不能画一个无限嵌套的三角形，所以我们需要定义一个边缘情况。为了做到这一点，我们可能有某种计数器，它将被设置为我们想要拥有的嵌套级别的数量，然后它的数量将随着每次递归调用而减少，最终变为零。将这样的计数器称为『复杂性级别』在直觉上是合理的。

现在我们可以定义绘制复杂度为 $n$ 的谢尔宾斯基三角形的过程如下：如果 $n$ 为零，则只绘制一个等边三角形，否则绘制一个等边三角形，内部有三个复杂度为 $n - 1$ 的谢尔宾斯基三角形。

这是一个可行的实现：

from turtle import Turtle, exitonclick


def sierpinski(turtling, length, complexity):
    if not complexity:
        for i in range(3):
            turtling.forward(length)
            turtling.left(120)
    else:
        # 绘制左下小三角形
        sierpinski(turtling, length / 2, complexity - 1)

        turtling.forward(length / 2)

        # 绘制右下小三角形
        sierpinski(turtling, length / 2, complexity - 1)

        turtling.left(120)
        turtling.forward(length / 2)
        turtling.rt(120)

        # 绘制上方小三角形
        sierpinski(turtling, length / 2, complexity - 1)

        # 返回初始位置
        turtling.left(60)
        turtling.back(length / 2)
        turtling.right(60)


if __name__ == "__main__":
    swifty = Turtle()
    # 复杂度3及以上需要这个设置
    swifty.speed("fastest")
    sierpinski(swifty, 200, 3)
    exitonclick()

建议自行运行代码或观看相关动画，更深入地掌握递归程序的过程。这里只是一些静态图片，结果图具有不同的初始复杂度级别。

不同复杂度的谢尔宾斯基三角形

除了某些绝不使用递归的特定任务，有时递归不会对效率产生显著影响，但会使您的代码更加直观、清晰和可读。乍一看，这似乎是一个奇怪的陈述，但有时以递归方式解释某些事情会更自然。一个例子是阶乘函数，它是从 $1$ 到给定正整数的所有整数的乘积^[10]。可以这样编写此函数：要计算给定数字 $n$ 的阶乘，您需要将累加器设置为 $1$ ，然后将累加值迭代地乘以数字 $2, 3, \dots$ 直到 $n$ ，即

n! = \prod_{x = 1}^{n} x

def factorial(n):
    res = 1
    for i in range(2, n+1):
        res *= i 
    return res

或者人们可以将其改写成更接近数学定义的形式：如果 $n = 0$ ，则给定数字 $n$ 的阶乘 $n! = 0! = 1$ ，否则为 $n! = n \cdot (n - 1)!$ 。

def ffactorial(n):
    return 1 if not n else n * ffactorial(n-1)

正如您所看到的，这些功能本质上是相同的东西，但我们从不同的角度去实现它们。在这种情况下使用递归不会太严重地损害效率。但是，我之前已经提到过一些您希望在这种情况下避免使用递归的原因。在关于列表处理函数的另一课中，描述了执行此类计算的另一种方法，它不存在人为实现的循环。

第4部分 - 有时这仍然是一个坏主意

尽管如此，在阶乘的情况下使用递归还不错。这是因为每次进行递归调用时，我们都会移动到新的输入值并逐渐向边缘情况移动。具有这种递归计算过程模式的函数称为线性递归，这是因为在整个计算过程中调用函数的输入序列形成了一个从初始参数到边缘情况参数的链。还有其他递归模式称为非线性递归，直接计算非线性递归函数会导致灾难性的效率损失。

一个众所周知的例子是一个返回第 $n$ 个斐波那契数的函数。斐波那契数列的定义如下：第 $0$ 个和第 $1$ 个数字是 $1$ ，后面的所有数字都是它们之前的两个数字之和，即

f (n) = f (n - 1) + f (n - 2)

因此，为了得到第 $2$ 个数字，我们需要计算 $f (2) = f (0) + f (1) = 1 + 1 = 2$ ，以此类推。再一次，有两种可能的实现来同样的事情。

def fib(n):
    a, b = 1, 1
    for i in range(n):
        a, b = b, a + b
    return a


def ffib(n):
    print('fib({})'.format(n))
    return 1 if n in (0, 1) else ffib(n - 1) + ffib(n - 2)

但让我们看看第2种递归实现的函数调用序列：

print(ffib(5))
>>> ffib(5)
..| fib(5)
..| fib(4)
..| fib(3)
..| fib(2)
..| fib(1)
..| fib(0)
..| fib(1)
..| fib(2)
..| fib(1)
..| fib(0)
..| fib(3)
..| fib(2)
..| fib(1)
..| fib(0)
..| fib(1)
..| 8

正如您所看到的，有很多重复，并且很清楚为什么会发生这种情况：为了计算第7个斐波那契数，我们需要计算第6个和第5个。为了计算第6个，我们需要计算第5个和第4个。尽管稍后我们将需要这些值，但我们将按照定义函数的方式再次计算这些值。与使用第一种方法完成的迭代次数（等于我们传递的次数）相比，这显着增加了计算复杂性。因此在某些时候，使用简单的递归并不好不仅是由于 Python 特定的原因，而且在一般情况下都是不好的。一些方法可以在其他课程描述的功能范式中处理此类情况。

总结

这一节课，我们……

讲解了递归的使用方法，如何定义一个递归函数。
解释了为什么大多数 Python 开发者不喜欢使用递归，也说明了 Python 解释器在递归处理上的不足。
用了4个常见的例子，对比其迭代算法和递归算法的编写难度，充分体现了递归在此类问题上的优越性。
用1个反例说明递归思想仍有考虑不周的地方，按具体问题选择最佳的解决方案。

此处特指迭代式的循环。 ↩︎
假设我们已知headFunc()和后续剩余部分的计算结果。 ↩︎
比如阿克曼函数（非原始递归函数的典例，教科书中有时也将其叫做双递归函数）。尽管知乎里有不少的观点认为所有的递归算法都可以将其非递归化，但仍然需要人工维护一个栈结构。个人认为这些函数的非递归化意义不大。 ↩︎
我只知道 Scala 会有这种优化，不知道原作者是否使用过其他具备函数式编程能力的语言。 ↩︎
我的环境默认设定为 1000 。 ↩︎
并抛出一个RecursionError异常，其内容为maximum recursion depth exceeded。 ↩︎
sys.setrecursionlimit()方法可以修改最大递归深度限制。 ↩︎
部分教材或网页也会将其称为河内塔。 ↩︎
边长为大三角形的一半，至少有1个顶点与大三角形的1个顶点重合，与顶点相邻的2条边不相交。 ↩︎
这个定义只是对正整数而言的，其他数就是另外定义产生的解析延拓了。 ↩︎