理解 Python 中的递归函数

作为一名专业程序员，您需要在变量、条件语句、数据类型、访问说明符、函数调用、作用域等基础方面做到扎实。不管您在写什么样的程序——无论是中间件程序、Web 开发还是数据科学——这些都是您作为程序员必须非常熟悉的最基本内容。首先，您是程序员，其次才是数据科学家、Web 开发者或机器学习工程师等。

其中一个这样的基础概念就是递归，当您在编写某类函数时，了解它至关重要。您可能已经知道：“当一个函数调用自身时，称为递归。”但底层到底发生了什么？递归会如何影响物理内存？是否可以把每个函数都改写为递归函数？在本教程中，您将找到这些基本问题的答案。

递归函数的结构：

您或许已经在计算机科学或信息技术的本科课程中接触过递归这个术语。本节将以一种更有趣的方式重温这些概念。我们开始吧。

让我们再次回到递归的定义：“当一个函数调用自身时，称为递归”。用一个例子来支撑这个定义：

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}
技术支持

您可以看到函数 A() 在调用自身。这是递归的一个例子，A() 是一个递归函数。

现在我们来学习一下递归函数的一些基础。

递归函数的基础：

一个递归函数必须包含以下两个要素：

递推关系
终止条件

参考上面的代码片段来理解这些要点。显然，该函数具有特定的递推关系：

$n\le 1$ 是终止条件 / 锚点条件 / 基例条件，满足该条件时递归停止。明确这一条件至关重要，否则函数将陷入无限循环。

（请注意，上面的代码片段不遵循任何特定的编程语言。此处的主要意图是展示一个递归函数的示例。）

您也许会想，既然有更好的替代方案，为什么还要写递归函数？是的，有时跟踪递归确实很难，但一旦熟悉了这种实践，您会发现递归在程序可读性和变量处理方面非常优雅。递归的执行不需要额外的变量，但它需要一个恰当的终止条件来停止。很多时候，找到递归的终止条件并不容易。不过，“熟能生巧”。在本教程的后面，您将看到如果用递归来实现，程序可以多么简洁而优美。现在，您将继续学习递归函数的内存表示。

递归函数的内存表示：

在本节中，您将学习递归函数如何以树和栈的方式在内存中进行基础表示。我们以下面的递归函数 A() 为例进行说明：

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}
技术支持

您将先用树来理解内存表示。这听起来可能有点难，但其实很直接。如果把每次函数调用按树状方式写出来，会是什么样子？

大概如下所示：

这里有几点需要注意：

函数以 A(3) 调用，因此这里一共发生了 4 次（3+1）函数调用。一般化来说，如果调用 A(n)，则总共会需要（n+1）次函数调用。
P() 调用表示由 print(n) 产生的打印。
当函数调用到 A(0) 时停止，因为 A(0) 之后的 if 语句将接收到 n < 1，从而导致函数终止。

之所以先展示这种树状表示，是因为在用栈来表示递归函数时，需要用到这种表示。下面将看到这一点。

（栈是一种数据结构，遵循后进先出（LIFO）的顺序）

对于栈的表示，您需要以自上而下、从左到右的顺序遍历这棵树。下图可以说明这一点。

如何解读这个看起来有点奇怪的东西（树）。请记住，栈包含两种操作——1. Push（入栈），用于将元素插入栈中；2. Pop（出栈），用于将元素从栈中取出。

现在，您以自上而下、从左到右的顺序开始树的遍历：

每当遇到一次函数调用，您就将其压入栈中。
如果遇到 print() / P() 调用，则按遍历遇到的顺序直接打印相应的元素。

以下是按自上而下的方式，从 A(3) 到 A(0) 遍历树时，栈中的元素：

现在开始树遍历的后半程，即从左到右。当您第二次遇到某个函数调用时，将其弹出（pop）。有趣的是，栈中第一个被弹出的元素（A(0)）恰恰是最后进入栈的那个（还记得 LIFO 吗？）。接着，您会遇到三个 P() 调用——P(1)、P(2) 和 P(3)。您将按遍历过程中遇到它们的顺序进行打印。顺序为：

1 2 3

最后，当您完成遍历过程时，栈将被完全清空。为了更好地理解出栈操作，下面是一张栈被完全弹空后的图示。

您已经看到了如何用树和栈把一个简单的递归函数表示到内存中。现在，将看看如何跟踪一次递归。

跟踪一次递归：

本节将学习如何有条不紊地跟踪一次递归。请看下面的递归函数：

void A(n){
    if(n>0){
        print(n-1);
        A(n-1);
    }
}
技术支持

这里有一个关键点——每当一个函数被调用时，内存中都会创建一个激活记录（activation record），其中包含该函数的局部变量以及一个指令指针（表示当调用返回到该函数时要执行的下一步任务）。假设一个名为 main() 的函数以 A(3) 的形式调用了上述函数 A()。为方便理解，让我们从 if 语句开始给 A() 的各行编号：

void A(n){
    1. if(n>0)
    2. {
        3. print(n-1);
        4. A(n-1);
    5. }
}
技术支持

激活记录如下所示：

如前所述，函数各自拥有局部变量和指令指针（在这里是行号）。在 A(0) 之后，函数 A() 将终止，并开始弹栈。请注意，这里使用的是水平展示的栈，与您之前在教程中看到的完全相同。在记录被压入栈的同时，打印也会发生，并且将打印以下元素：

2 1 0

这里指令指针非常重要，因为在递归函数中，控制流常常会返回到同一个函数，但变量值不同。为了保持一切同步，这些指针确实很有帮助。您可以按照完全相同的过程，借助树形表示来跟踪一次递归。

接下来将学习如何对递归函数进行空间-时间分析。

递归函数的空间-时间分析：

DataCamp 有一篇关于Python 中的渐进分析的优秀文章，建议在阅读本节之前先了解一下。让我们快速回顾一下函数的空间和时间分析（也称为空间复杂度和时间复杂度）的含义：

对于给定输入，函数应产生某种输出。为此函数需要花费多少时间？时间复杂度度量对这段时间进行近似，也称为函数的运行时间。同样，空间复杂度则近似地度量函数对空间（内存）的需求，即针对给定输入的情况。那么为什么需要这些度量？

无需在不同规模的输入范围上实际运行函数，您就可以近似判断一个函数在不同规模输入上的表现。
如果您有两个实现相同目标的函数，应当选择哪一个？您会依据哪些指标来做决定？没错，您将通过分析它们的空间和时间复杂度来比较，看看哪一个表现更好。

现在我们取一个简单的递归函数来分析其空间和时间复杂度。

void A(n){
    if(n>1) // Anchor condition
    {
       return A(n-1);
    }
}
技术支持

先做时间复杂度分析。假设上述函数 A() 的总耗时为 $T(n)$。那么 $T(n)$ 等于比较 n 是否大于 1 的时间与执行 A(n-1) 的时间之和。因此，$T(n)$ 可表示为——

$T(n)$ = 1 + $T(n-1)$

其中 1 表示比较所需的时间（您也可以用任意常数）。那么，执行 A(n-1) 的时间（用 $T(n)$ 表示）是多少？

$T(n-1)$ = 1 + $T(n-2)$

同理，

$T(n-2)$ = 1 + $T(n-3)$

以此类推。

如果仔细观察这些等式，彼此之间是相连的，不是吗？如果依次代入，您会得到——

$T(n)$ = 1 + (1 + $T(n-2)$) = 2 + $T(n-2)$ = 3 + $T(n-3)$ = .... = k + $T(n-k)$（运行到第 k 项时）

现在，您需要确定函数在何处停止。根据给定的锚点条件，可以写出——

假设在运行到第 k 项时，函数停止。如果是这样，那么必有——

$n - k = 1 => k = n - 1$

现在将 k（= n - 1）的值代入 $T(n) = k + T(n-k)$：

$T(n) = (n-1) + T(n-(n-1))$
$=> T(n) = (n-1) + T(1)$
$=> T(n) = n-1 + 1 = n$ // 对于 T(1) 只需进行比较

按照渐进分析的规则，$T(n) = n$ 可写为 $T(n) = \mathcal{O}(n)$。这意味着该函数的（最坏）时间复杂度是 $\mathcal{O}(n)$。

此处您或许需要稍微放慢速度，仔细观察这一过程的每一步。强烈建议您用纸笔演算一遍，以便理解每个细节。

该函数的空间复杂度分析很简单。此函数是在内存中进行的，不使用任何额外变量。因此，可以得出该函数的空间复杂度为 $\mathcal{O}(n)$。

现在，您将把这些内容综合起来，在 Python 中实现一个简单的递归函数。

在 Python 中实现一个简单的递归函数：

您将编写一个递归函数来求给定数字的阶乘。然后再编写该函数的迭代版本。我们开始吧。

# Recursive function factorial_recursion()

def factorial_recursion(n):  
   if n == 1:  
       return n  
   else:  
       return n*factorial_recursion(n-1)
技术支持

# Call the function

num = 7
print("The factorial of ",num," is ",factorial_recursion(num))
技术支持

The factorial of  7  is  5040
技术支持

还记得编写递归函数的两个关键要素吗？

递推关系
终止条件

在这里，递推关系可以是：

$f(n) = n!$
$f(n) = n * f(n-1)$，以此类推。

终止条件是 n 等于 1 时。

很简单，对吧？

现在，您将实现同一函数的迭代版本。

def factorial_iterative(num):
    factorial = 1
    if num < 0:
        print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1,num + 1):
           factorial = factorial*i
        print("The factorial of",num,"is",factorial)
技术支持

factorial_iterative(7)
技术支持

The factorial of 7 is 5040
技术支持

您可以清楚地看出两种版本之间的差异。递归版本比迭代版本要优雅得多。不是吗？

恭喜！

您已经读到了最后。在本教程中，您系统地学习了递归函数。从最基础的内容到对递归函数的空间和时间复杂度进行分析，您都已覆盖。您还看到了，递归对于具有某种特征的问题是如何发挥作用的。现在，您应该能够使用递归来解决具有（递推关系和终止条件）的问题了。您或许还想尝试用递归在一定范围内求解斐波那契数的问题。

我建议您使用递归来解决一些常见问题，如二分查找、归并排序、汉诺塔等，并进行空间-时间分析。这无疑会让您成为更优秀的程序员。

从入门的角度来看，以上内容已经足够。但如果您想进一步学习递归，请务必访问以下链接：

如果您想进一步学习 Python，可以参加 DataCamp 的免费课程 Intro to Python for Data Science。

主题

Python 数据科学数据分析

主题

技术

理解 Python 中的递归函数

使用 AI 探索