Python 中的递归：简介

目录

如果您熟悉Python 中的函数，那么您就会知道一个函数调用另一个函数是很常见的。在 Python 中，函数也可以调用自身！调用自身的函数被说成是递归的，并且采用递归函数的技术称为递归。

函数调用自身可能看起来很奇怪，但许多类型的编程问题最好以递归方式表达。当您遇到这样的问题时，递归是您工具箱中不可或缺的工具。

在本教程结束时，您将了解：

• 函数递归调用自身意味着什么
• Python 函数的设计如何支持递归
• 选择是否递归解决问题时需要考虑哪些因素
• 如何在 Python 中实现递归函数

然后，您将学习几个使用递归的 Python 编程问题，并将递归解决方案与可比较的非递归解决方案进行对比。

什么是递归？

递归这个词来自拉丁词recurrere，意思是奔跑或加速返回、返回、恢复或递归。以下是递归的一些在线定义：

• Dictionary.com :返回或跑回的行为或过程
• 维基词典：根据对象本身定义对象（通常是函数）的行为
• 自由词典：一种定义对象序列的方法，例如表达式、函数或集合，其中给出了一定数量的初始对象，并且每个后续对象都根据前面的对象进行定义

甲递归定义是其中所定义的术语出现在定义本身。自我指涉的情况经常出现在现实生活中，即使它们不能立即被识别出来。例如，假设您想描述构成您祖先的一组人。你可以这样描述它们：

注意正在定义的概念，祖先，如何在它自己的定义中出现。这是一个递归定义。

在编程中，递归具有非常精确的含义。它指的是一种函数调用自身的编码技术。

为什么要使用递归？

大多数编程问题无需递归即可解决。所以，严格来说，递归通常是没有必要的。

然而，有些情况特别适合自我参照的定义——例如，上面显示的祖先的定义。如果您正在设计一种算法来以编程方式处理这种情况，那么递归解决方案可能会更清晰、更简洁。

树状数据结构的遍历是另一个很好的例子。因为这些是嵌套结构，所以它们很容易适合递归定义。遍历嵌套结构的非递归算法可能有点笨拙，而递归解决方案将相对优雅。本教程稍后将提供一个示例。

另一方面，递归并不适用于所有情况。以下是一些需要考虑的其他因素：

• 对于某些问题，尽管可能，递归解决方案将是笨拙而不是优雅的。
• 递归实现通常比非递归实现消耗更多的内存。
• 在某些情况下，使用递归可能会导致执行时间变慢。

通常，代码的可读性将是最大的决定因素。但这取决于具体情况。下面提供的示例应该可以帮助您了解何时应该选择递归。

Python 中的递归

当您在 Python 中调用函数时，解释器会创建一个新的本地命名空间，以便在该函数中定义的名称不会与其他地方定义的相同名称发生冲突。一个函数可以调用另一个函数，即使它们都定义了同名的对象，这一切都很好，因为这些对象存在于不同的命名空间中。

如果同一函数的多个实例同时运行，则同样如此。例如，考虑以下定义：

def function():
    x = 10
    function()

当function()执行第一次，Python中创建一个命名空间和分配x的值10在该命名空间。然后function()递归调用自身。第二次function()运行时，解释器创建第二个命名空间并分配10给x那里。名称的这两个实例x彼此不同，并且可以共存而不会发生冲突，因为它们位于不同的名称空间中。

不幸的是，function()按原样运行产生的结果并不鼓舞人心，如下回溯所示：

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

正如所写的function()那样，理论上会永远持续下去，一遍又一遍地调用自己，而没有任何调用返回。当然，在实践中，没有什么是真正永恒的。您的计算机只有这么多内存，最终会耗尽。

Python 不允许这种情况发生。解释器限制了函数可以递归调用自身的最大次数，当达到该限制时，它会引发RecursionError 异常，如上所示。

>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

一个函数不加区别地无休止地递归调用自己并没有多大用处。这让人想起您有时会在洗发水瓶上看到的说明：“起泡、冲洗、重复。” 如果你从字面上遵循这些说明，你会永远洗头发！

这种逻辑缺陷显然发生在一些洗发水制造商身上，因为有些洗发水瓶上写着“泡沫，冲洗，必要时重复”。这为指令提供了终止条件。大概，你最终会觉得你的头发足够干净，不需要额外的重复。然后可以停止洗发。

同样，递归调用自身的函数必须有一个最终停止的计划。递归函数通常遵循以下模式：

• 有一个或多个基本情况可以直接解决而无需进一步递归。
• 每个递归调用使解决方案逐渐接近基本情况。

您现在已准备好通过一些示例了解它是如何工作的。

开始：倒数到零

第一个示例是一个名为 的函数countdown()，它接受一个正数作为参数并打印从指定参数到零的数字：

>>> def countdown(n):
...     print(n)
...     if n == 0:
...         return             # Terminate recursion
...     else:
...         countdown(n - 1)   # Recursive call
...

>>> countdown(5)
5
4
3
2
1
0

请注意countdown()上述递归算法的范式是如何拟合的：

• 基本情况发生在n0 时，此时递归停止。
• 在递归调用中，参数比 的当前值小 1 n，因此每次递归都更接近基本情况。

countdown()上面显示的版本清楚地突出了基本情况和递归调用，但有一种更简洁的表达方式：

def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)

这是用于比较的一种可能的非递归实现：

>>> def countdown(n):
...     while n >= 0:
...         print(n)
...         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0

在这种情况下，非递归解决方案至少与递归解决方案一样清晰直观，而且可能更是如此。

计算因子

下一个示例涉及阶乘的数学概念。正整数n的阶乘，表示为n !，定义如下：

换句话说，n！是从 1 到n的所有整数的乘积，包括端值。

阶乘如此适用于递归定义，以至于编程文本几乎总是将其作为第一个示例之一。你可以表达n的定义！像这样递归：

与上面显示的示例一样，有些基本情况无需递归即可解决。更复杂的情况是reductive，这意味着它们减少到基本情况之一：

• 基本情况（n = 0 或n = 1）无需递归即可解决。
• 对于大于 1的n值，n ! 是根据 ( n - 1)!定义的，因此递归解决方案逐渐接近基本情况。

例如，递归计算 4! 看起来像这样：

4!, 3!, 和 2! 的计算 暂停，直到算法达到n = 1的基本情况。此时，1！无需进一步递归即可计算，并且延迟计算会一直运行到完成。

定义 Python 阶乘函数

这是一个用于计算阶乘的递归 Python 函数。请注意它是多么简洁以及它如何很好地反映了上面显示的定义：

>>> def factorial(n):
...     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24

用一些print()语句稍微修饰这个函数，可以更清楚地了解调用和返回序列：

>>> def factorial(n):
...     print(f"factorial() called with n = {n}")
...     return_value = 1 if n <= 1 else n * factorial(n -1)
...     print(f"-> factorial({n}) returns {return_value}")
...     return return_value
...

>>> factorial(4)
factorial() called with n = 4
factorial() called with n = 3
factorial() called with n = 2
factorial() called with n = 1
-> factorial(1) returns 1
-> factorial(2) returns 2
-> factorial(3) returns 6
-> factorial(4) returns 24
24

注意所有递归调用是如何叠加的。在任何调用返回之前，该函数将使用n= 4、3、2和1连续调用。最后，当n是 时1，无需再递归即可解决问题。然后，每个堆叠的递归调用都展开返回1，返回、2、6，最后24从最外层调用返回。

这里不需要递归。您可以factorial()使用for循环迭代实现：

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

>>> factorial(4)
24

您还可以使用 Python 的 实现阶乘reduce()，您可以从模块中导入它functools：

>>> from functools import reduce
>>> def factorial(n):
...     return reduce(lambda x, y: x * y, range(1, n + 1) or [1])
...

>>> factorial(4)
24

timeit(<command>, setup=<setup_string>, number=<iterations>)

>>> from timeit import timeit

>>> timeit("print(string)", setup="string='foobar'", number=100)
foobar
foobar
foobar
   .
   . [100 repetitions]
   .
foobar
0.03347089999988384

>>> setup_string = """
... print("Recursive:")
... def factorial(n):
...     return 1 if n <= 1 else n * factorial(n - 1)
... """

>>> from timeit import timeit
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
Recursive:
4.957105500000125

接下来是迭代实现：

>>> setup_string = """
... print("Iterative:")
... def factorial(n):
...     return_value = 1
...     for i in range(2, n + 1):
...         return_value *= i
...     return return_value
... """

>>> from timeit import timeit
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
Iterative:
3.733752099999947

最后，这是使用的版本reduce()：

>>> setup_string = """
... from functools import reduce
... print("reduce():")
... def factorial(n):
...     return reduce(lambda x, y: x * y, range(1, n + 1) or [1])
... """

>>> from timeit import timeit
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
reduce():
8.101526299999932

在这种情况下，迭代实现是最快的，尽管递归解决方案也不甘落后。使用的方法reduce()是最慢的。如果您在自己的机器上尝试这些示例，您的里程可能会有所不同。您肯定不会获得相同的次数，甚至可能无法获得相同的排名。

有关系吗？迭代实现和使用 的实现之间的执行时间相差近四秒reduce()，但需要一千万次调用才能看到它。

如果您将多次调用一个函数，则在选择实现时可能需要考虑执行速度。另一方面，如果函数的运行频率相对较低，则执行时间的差异可能可以忽略不计。在这种情况下，您最好选择似乎最清楚地表达问题解决方案的实现。

对于阶乘，上面记录的时间表明递归实现是一个合理的选择。

坦率地说，如果您使用 Python 进行编码，则根本不需要实现阶乘函数。它已经在标准math模块中可用：

>>> from math import factorial
>>> factorial(4)
24

也许您可能有兴趣了解它在计时测试中的表现：

>>> setup_string = "from math import factorial"

>>> from timeit import timeit
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
0.3724050999999946

哇！math.factorial()性能比上面显示的其他三个实现中最好的要好大约 10 倍。

用 C 实现的函数实际上总是比用纯 Python 实现的相应函数快。

遍历嵌套列表

下一个示例涉及访问嵌套列表结构中的每个项目。考虑以下 Python列表：

names = [
    "Adam",
    [
        "Bob",
        [
            "Chet",
            "Cat",
        ],
        "Barb",
        "Bert"
    ],
    "Alex",
    [
        "Bea",
        "Bill"
    ],
    "Ann"
]

如下图所示，names包含两个子列表。这些子列表中的第一个本身包含另一个子列表：

假设您想计算此列表中的叶元素（最低级别的str对象）的数量，就好像您已经展平了列表一样。叶元素是"Adam", "Bob", "Chet", "Cat", "Barb", "Bert", "Alex", "Bea", "Bill", 和"Ann"，所以答案应该是10。

只是调用len()列表并不能给出正确的答案：

>>> len(names)
5

len()在计数的顶层对象names，这是三个簧片元件"Adam"，"Alex"以及"Ann"和两个子列表["Bob", ["Chet", "Cat"], "Barb", "Bert"]和["Bea", "Bill"]：

>>> for index, item in enumerate(names):
...     print(index, item)
...
0 Adam
1 ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert']
2 Alex
3 ['Bea', 'Bill']
4 Ann

这里你需要的是一个遍历整个列表结构的函数，包括子列表。算法是这样的：

1. 遍历列表，依次检查每个项目。
2. 如果找到叶元素，则将其添加到累积计数中。
3. 如果遇到子列表，请执行以下操作：
   • 下拉到该子列表并类似地遍历它。
   • 用完子列表后，返回，将子列表中的元素添加到累积计数中，然后从上次停止的地方继续遍历父列表。

请注意此描述的自我引用性质：遍历列表。如果您遇到子列表，则类似地遍历该列表。这种情况需要递归！

递归遍历嵌套列表

递归非常适合这个问题。要解决它，您需要能够确定给定的列表项是否为叶项。为此，您可以使用内置的 Python 函数isinstance()。

在names列表的情况下，如果一个项目是 type 的实例list，那么它就是一个子列表。否则，它是一个叶项：

>>> names
['Adam', ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert'], 'Alex', ['Bea', 'Bill'], 'Ann']

>>> names[0]
'Adam'
>>> isinstance(names[0], list)
False

>>> names[1]
['Bob', ['Chet', 'Cat'], 'Barb', 'Bert']
>>> isinstance(names[1], list)
True

>>> names[1][1]
['Chet', 'Cat']
>>> isinstance(names[1][1], list)
True

>>> names[1][1][0]
'Chet'
>>> isinstance(names[1][1][0], list)
False

现在，您已经有了工具来实现对列表中的叶元素进行计数的函数，并以递归方式计算子列表：

def count_leaf_items(item_list):
    """Recursively counts and returns the
       number of leaf items in a (potentially
       nested) list.
    """
    count = 0
    for item in item_list:
        if isinstance(item, list):
            count += count_leaf_items(item)
        else:
            count += 1

    return count

如果你count_leaf_items()在多个列表上运行，包括names上面定义的列表，你会得到：

>>> count_leaf_items([1, 2, 3, 4])
4
>>> count_leaf_items([1, [2.1, 2.2], 3])
4
>>> count_leaf_items([])
0

>>> count_leaf_items(names)
10
>>> # Success!

与阶乘示例一样，添加一些print()语句有助于演示递归调用和返回值的序列：

 1def count_leaf_items(item_list):
 2    """Recursively counts and returns the
 3       number of leaf items in a (potentially
 4       nested) list.
 5    """
 6    print(f"List: {item_list}")
 7    count = 0
 8    for item in item_list:
 9        if isinstance(item, list):
10            print("Encountered sublist")
11            count += count_leaf_items(item)
12        else:
13            print(f"Counted leaf item \"{item}\"")
14            count += 1
15
16    print(f"-> Returning count {count}")
17    return count

以下是上面示例中发生的事情的概要：

• 第 9 行： isinstance(item, list) is True，所以count_leaf_items()找到了一个子列表。
• 第 11 行：该函数递归调用自身以计算子列表中的项目，然后将结果添加到累计总数中。
• 第 12 行： isinstance(item, list) is False，所以count_leaf_items()遇到了叶项。
• 第 14 行：该函数将累加总数加 1 以说明叶项。

count_leaf_items()它在names列表上执行时的输出现在看起来像这样：

>>> count_leaf_items(names)
List: ['Adam', ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert'], 'Alex', ['Bea', 'Bill'], 'Ann']
Counted leaf item "Adam"
Encountered sublist
List: ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert']
Counted leaf item "Bob"
Encountered sublist
List: ['Chet', 'Cat']
Counted leaf item "Chet"
Counted leaf item "Cat"
-> Returning count 2
Counted leaf item "Barb"
Counted leaf item "Bert"
-> Returning count 5
Counted leaf item "Alex"
Encountered sublist
List: ['Bea', 'Bill']
Counted leaf item "Bea"
Counted leaf item "Bill"
-> Returning count 2
Counted leaf item "Ann"
-> Returning count 10
10

每次调用count_leaf_items()终止时，它都会返回它在传递给它的列表中计算的叶元素计数。顶级调用返回10，正如它应该的那样。

非递归遍历嵌套列表

与目前显示的其他示例一样，此列表遍历不需要递归。您也可以迭代地完成它。这是一种可能性：

def count_leaf_items(item_list):
    """Non-recursively counts and returns the
       number of leaf items in a (potentially
       nested) list.
    """
    count = 0
    stack = []
    current_list = item_list
    i = 0

    while True:
        if i == len(current_list):
            if current_list == item_list:
                return count
            else:
                current_list, i = stack.pop()
                i += 1
                continue

        if isinstance(current_list[i], list):
            stack.append([current_list, i])
            current_list = current_list[i]
            i = 0
        else:
            count += 1
            i += 1

如果count_leaf_items()在前面显示的相同列表上运行此非递归版本，则会得到相同的结果：

>>> count_leaf_items([1, 2, 3, 4])
4
>>> count_leaf_items([1, [2.1, 2.2], 3])
4
>>> count_leaf_items([])
0

>>> count_leaf_items(names)
10
>>> # Success!

这里采用的策略使用堆栈来处理嵌套的子列表。当这个版本count_leaf_items()遇到一个子列表时，它会将当前正在进行的列表和该列表中的当前索引压入堆栈。一旦它对子列表进行了计数，该函数就会从堆栈中弹出父列表和索引，以便它可以从停止的地方继续计数。

事实上，本质上同样的事情也发生在递归实现中。当您递归调用函数时，Python 将执行实例的状态保存在堆栈上，以便递归调用可以运行。当递归调用完成时，状态从堆栈中弹出，以便被中断的实例可以恢复。这是相同的概念，但使用递归解决方案，Python 正在为您完成状态保存工作。

请注意与非递归版本相比，递归代码的简洁性和可读性：

递归 vs 非递归嵌套列表遍历

>>> def is_palindrome(word):
...     """Return True if word is a palindrome, False if not."""
...     return word == word[::-1]
...

>>> is_palindrome("foo")
False
>>> is_palindrome("racecar")
True
>>> is_palindrome("troglodyte")
False
>>> is_palindrome("civic")
True

>>> def is_palindrome(word):
...     """Return True if word is a palindrome, False if not."""
...     if len(word) <= 1:
...         return True
...     else:
...         return word[0] == word[-1] and is_palindrome(word[1:-1])
...

>>> # Base cases
>>> is_palindrome("")
True
>>> is_palindrome("a")
True

>>> # Recursive cases
>>> is_palindrome("foo")
False
>>> is_palindrome("racecar")
True
>>> is_palindrome("troglodyte")
False
>>> is_palindrome("civic")
True

使用快速排序进行排序

呈现的最后一个例子，如嵌套列表遍历，是一个很好的例子，它很自然地暗示了递归方法。该快速排序算法是由英国计算机科学家托尼·霍尔于1959年开发出一种高效排序算法。

快速排序是一种分而治之的算法。假设您有一个要排序的对象列表。您首先在列表中选择一个项目，称为枢轴项目。这可以是列表中的任何项目。然后，分区列表到基于枢轴项中包含两个子列表和递归排序的子列表。

该算法的步骤如下：

• 选择枢轴项。
• 将列表分成两个子列表：
  1. 那些小于枢轴项的项
  2. 那些大于枢轴项的项
• 递归快速排序子列表。

每个分区产生较小的子列表，因此该算法是还原的。当子列表为空或只有一个元素时，会出现基本情况，因为它们是固有排序的。

另一方面，如果您选择的主元项特别不走运，则每个分区都会产生一个包含除主项之外的所有原始项的子列表和另一个为空的子列表。在这种情况下，将列表减少到基本情况需要七个步骤：

使用快速排序实现

现在基础工作已经准备就绪，您可以继续使用 Quicksort 算法了。这是 Python 代码：

 1import statistics
 2
 3def quicksort(numbers):
 4    if len(numbers) <= 1:
 5        return numbers
 6    else:
 7        pivot = statistics.median(
 8            [
 9                numbers[0],
10                numbers[len(numbers) // 2],
11                numbers[-1]
12            ]
13        )
14        items_less, pivot_items, items_greater = (
15            [n for n in numbers if n < pivot],
16            [n for n in numbers if n == pivot],
17            [n for n in numbers if n > pivot]
18        )
19
20        return (
21            quicksort(items_less) +
22            pivot_items +
23            quicksort(items_greater)
24        )

这是每个部分quicksort()正在做的事情：

• 第 4 行：列表为空或只有一个元素的基本情况
• 第 7 行到第 13 行：通过中值三法计算枢轴项
• 第 14 到 18 行：创建三个分区列表
• 第 20 到 24 行：分区列表的递归排序和重组

以下是一些quicksort()在行动中的例子：

>>> # Base cases
>>> quicksort([])
[]
>>> quicksort([42])
[42]

>>> # Recursive cases
>>> quicksort([5, 2, 6, 3])
[2, 3, 5, 6]
>>> quicksort([10, -3, 21, 6, -8])
[-8, -3, 6, 10, 21]

出于测试目的，您可以定义一个简短的函数来生成1和之间的随机数列表100：

import random

def get_random_numbers(length, minimum=1, maximum=100):
    numbers = []
    for _ in range(length):
        numbers.append(random.randint(minimum, maximum))

    return numbers

现在您可以使用get_random_numbers()来测试quicksort()：

>>> numbers = get_random_numbers(20)
>>> numbers
[24, 4, 67, 71, 84, 63, 100, 94, 53, 64, 19, 89, 48, 7, 31, 3, 32, 76, 91, 78]
>>> quicksort(numbers)
[3, 4, 7, 19, 24, 31, 32, 48, 53, 63, 64, 67, 71, 76, 78, 84, 89, 91, 94, 100]

>>> numbers = get_random_numbers(15, -50, 50)
>>> numbers
[-2, 14, 48, 42, -48, 38, 44, -25, 14, -14, 41, -30, -35, 36, -5]
>>> quicksort(numbers)
[-48, -35, -30, -25, -14, -5, -2, 14, 14, 36, 38, 41, 42, 44, 48]

>>> quicksort(get_random_numbers(10, maximum=500))
[49, 94, 99, 124, 235, 287, 292, 333, 455, 464]
>>> quicksort(get_random_numbers(10, 1000, 2000))
[1038, 1321, 1530, 1630, 1835, 1873, 1900, 1931, 1936, 1943]

要进一步了解quicksort()工作原理，请参见下图。这显示了对十二元素列表进行排序时的递归序列：

快速排序算法，十二元素列表