Python 中的递归

2021-06-03

什么是递归

递归（recursion）这个单词来自拉丁语中的 recurre，意思是：匆匆而归、返回、还原或重现。以下是网络上对递归的一些定义：

Dictionary.com：表示返回的行为或过程。
Wiktionary ：在对象内部定义使用该对象（通常是函数）的操作。
The Free Dictionary：定义一系列对象的方法，如表达式、函数、集合等，给定一些初始对象，并且根据根据前面的对象来定义后续每个对象。

所谓递归，是指被定义的对象出现在定义本身中。在现实生活中经常会出现自我参照的情况，尽管这种情况没有立即被识别出来。例如，假设定义祖先，可以用这样的表达式：

祖先 = （父母） + （父母的祖先）

请注意上述定义中的祖先，在它自己的定义中也出现。这是一个递归的定义。

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

为什么使用递归？

大多数编程问题是不需要递归就可以解决的。所以严格说来，递归通常是不必须的。

然而，有些情况特别适合用自我参照进行定义，例如，上面所示的“祖先”的定义，如果你要写一段程序实现这个定义，用递归可能是一种简约的途径。

对树状数据结构的遍历也是应用递归的恰当例子。因为这类数据是嵌套结构，很容易用递归定义。遍历嵌套结构的非递归算法可能会有点笨拙，而递归解决方案则相对优雅。

另一方面，递归并非对每一种情况都适用。以下是需要考虑的其他因素：

有些问题虽然可以使用递归方案来解决，但实际上会显得很笨拙，而不是优雅。
递归实现通常比非递归实现消耗更多的内存。
在某些情况下，使用递归可能会导致执行时间较长。

通常，代码的可读性是编程中应该考虑的第一因素。是否使用递归，要视具体情况而定。下面的示例将帮助你了解何时应该选择递归。

Python 中的递归

当你在 Python 中调用一个函数时，解释器会创建一个新的局部命名空间，这样在该函数中定义的名称就不会与其他地方定义的相同名称冲突。一个函数可以调用另一个函数，即使它们都定义了具有相同名称的对象，也能正常工作，因为这些对象存在于单独的命名空间中。

这一点同样适用于在同一函数中同时运行多个实例。例如以下定义:

1
2
3

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() 函数在理论上将永远持续下去，一遍又一遍地调用自己，而没有任何返回值。当然，在实践中，应该没有这样的递归。电脑只有那么多内存，那些内存最终也会耗尽。

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

技术说明：可以通过名 sys 模块中的 getrecursionlimit() 函数来了解 Python 的递归次数限制：

1
2
3

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

以上是限制的默认值，也可以通过 setrecursionlimit() 函数修改此值。

>>> 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() 函数的终止条件：

当 n 为零时，符合终止条件，此时递归停止。
在递归调用中，参数为 n-1 （ n 是当前值），因此每个递归都更接近终止条件。

注意：为简单起见，countdown() 不检查其参数的有效性。如果 n 是非整数或负数，则会出现 RecursionError 异常，因为它完全不不符合终止条件。

上面的 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\times2\times\cdots\times n$$

换句话说，$n！$ 是从 $1$ 到 $n$ 的所有整数的乘积。

因此，阶乘适合于用递归定义，很多编程的数据都会用这个作为示例说明递归。

$$n!=\begin{cases}1 & n=0,1\n\times(n-1)! & n\ge 2\end{cases}$$

与上面的示例一样，终止条件是不需要递归就可以实现的；更复杂的事件则可简化，也就是将其简化为终止条件之一:

$n = 0$ 或 $n = 1$ 时是终止条件，不需要递归就可以得到阶乘的结果。
如果 $n\gt1$ ，根据 $(n - 1)!$ 来定义 $n!$ ，这样通过递归逐步接近终止条件。

例如 $4!$ 的递归计算过程是这样的：

计算 $4!$ 、$3!$ 和 $2!$ ，直到 $n = 1$ 时的终止条件结束递归。此时，无需进一步递归就可以计算 $1!$ 。后续的延迟计算将运行到最终完成。

编写阶乘函数

下面的函数就是按照以上四项编写的计算阶乘的 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。

如果不用递归，其实也能实现阶乘，下面用 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 模块中的 timeit() 的函数，这个函数支持多种不同的调用形式，此处将用下面的方式调用:

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

执行 timeit() 函数时，首先调用 setup 参数的值 <setup_string> 中指令，然后按照 number 参数的值执行 <command> 操作 <iterations> 次，并报告累计的执行时间（以秒为单位）:

>>> from timeit import timeit

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

上述代码中，setup 参数实现了对变量 string 赋值为 foobar 的操作。然后将 print(string) 指令执行 number=100 次。最终显示执行时间是 0.03347 s （大于 $\frac{3}{100} s$ ）。

下面使用 timeit() 来比较上面实现阶乘三种方式：递归、for 循环和 reduce() 函数。在每种情况下，变量 setup_string 是字符串，其中定义了相关的 factorial() 函数。然后，timeit() 执行 factorial(4) 总共1000万次，并报告结果。

首先，测试递归版本:

>>> 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

接下来测试 for 循环的实现:

>>> 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

从上述测试可知，用 for 循环的迭代是最快的，尽管递归解决方案也不算太慢，倒是 reduce() 的实现是最慢的。如果你在自己的计算机上尝试这些示例，可能会有所不同。与示例相比，你所花费的时间肯定有所不同，甚至你所得出的排名也可能有所不同。

这有关系吗? 迭代和使用 reduce() 的实现在执行时间上几乎有4秒的差异，但我们需要1000万个调用才能看到这一差异。

如果要多次调用一个函数，那么在选择实现时可能需要考虑执行速度。另一方面，如果函数运行的频率相对较低，那么执行时间上的差异或许可以忽略不计。这种情况下，你所选择的实现最好能非常清楚地表达解决问题的方案——即代码的可读性是第一位的。

对于阶乘，从上述测试结果来看，递归实现是一个合理的选择。

坦白地说，如果你用 Python 编码，你根本不需要实现阶乘函数，因为标准库的 math 模块中已经提供了阶乘函数：

1
2
3

>>> 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 包含两个子列表。第一个子列表本身包含另一个子列表:

假设你想统计这个列表中叶子元素（即最低级别的字符串对象）的数量，就好像你已经将列表展开一样。叶子元素包括 "Adam"、"Bob"、"Chet"、"Cat"、"Barb"、"Bert"、"Alex"、"Bea"、"Bill"、"Ann" ，所以答案应该是“10”。

如果用 len() 函数并不能得出正确的答案：

1 2	>>> 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. 一旦你遍历了子列表，就返回，将子列表中的元素添加到累积计数中，并从结束的地方继续遍历父列表。

注意这里所描述的自引用性质: 遍历列表。如果遇到子列表，则用类似的方式遍历此列表，这种情况就需要递归!

用递归遍历嵌套列表

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

在 names 列表中，如果一个项是 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

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

def count_leaf_items(item_list):
    """Recursively counts and returns the
       number of leaf items in a (potentially
       nested) list.
    """
    print(f"List: {item_list}")
    count = 0
    for item in item_list:
        if isinstance(item, list):
            print("Encountered sublist")
            count += count_leaf_items(item)
        else:
            print(f"Counted leaf item \"{item}\"")
            count += 1

    print(f"-> Returning count {count}")
    return count

对上述示例的解释如下：

第9行: isinstance(item, list) 的值是 True ，所以 count_leaf_items() 找到了一个子列表。
*第11行: *函数通过调用自身实现递归，继续统计子列表中的项，然后将结果添加到累计的总数中。
*第12行: * isinstance(item, list) 的值是 False 时，count_leaf_items() 遇到了一个叶子项。
*第14行: *将累计总数增加1，以计入叶子项。

注：为简单起见, 该实现假设传递给 count_leaf_items() 的列表只包含叶子项或子列表, 而不包含任何其他类型的复合对象，如：字典或元组。

The output from count_leaf_items() when it’s executed on the names list now looks like this:

现在，对 names 列表执行 count_leaf_items() 时的输出是这样的:

>>> 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

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

        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!

这个函数中用栈来处理嵌套的子列表，当函数循环到一个子列表时，将父列表及子列表在父列表中的索引推送到栈里。一旦对子列表中的叶子元素完成计数，就会从栈中将父列表和索引删除并获得其返回值，这样就可以在停止的地方继续计算。

实际上，在递归实现中也会发生同样的事情。当你递归式调用函数时，Python 会将正在执行的实例的状态保存在栈上，以便可以运行递归调用。当递归调用完成时，状态将从栈中弹出，从而让中断的实例可以继续。这是相同的概念，但是在使用递归时，是 Python 自动完成了状态保存工作。

请注意，与非递归版本相比，递归代码是多么简洁易读：

比较递归式嵌套列表的遍历与非递归式嵌套列表的遍历

在这种情况下，使用递归绝对是一种优势。

检测回文

选择是否使用递归来解决问题在很大程度上取决于问题的性质。例如，阶乘自然可用递归实现，但用 for 循环也相当简单。这二者选谁，完全由开发者自己决定。

对于前面的遍历列表则是另一回事，对于该问题，显然递归非常优雅，而非递归解决方案则很麻烦。

下面再举一个检测回文的示例，如果使用递归解决这个问题，可以说是愚蠢的。

回文是一个单词，它从前往后读和从后往前读是一样的，例如：Racecar、Level、Kayak、Reviver、Civic

如果让你设计一个算法来判断一个字符串是否是回文的，你可能会想出类似于“反转字符串，看看它是否和原来一样”这样的方案——没有比这更简单的了。

>>> 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

这种方式又清楚又简洁。几乎不需要寻找替代方式。但为了好玩，请考虑一下用递归实现回文检测：

终止条件：空字符串以及单个字符，都可以视为回文。
递归：

长度大于或等于2个字符的字符串，如果同时满足以下两个条件，则为回文：
1. 第一个字符和最后一个字符相同。
2. 第一个字符和最后一个字符之间的子字符串是回文。

Slicing is your friend here as well. For a string word, indexing and slicing give the following substrings:

字符串的切片也是有帮助的。对于字符串 "word" ，索引和切片将给出以下子字符串：

第一个字符是 word[0] 。
最后一个字符是 word[-1] 。
第一个和最后一个字符之间的子字符串是 word[1:-1] 。

所以可以像下面这样用递归定义函数 is_palindrome() 来判断一个字符串是否为回文。

>>> 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

思考递归问题是一个有趣的练习，尽管它有时候不是很有必要。

Quicksort 排序

最后一个示例就像嵌套列表的遍历一样，是一个很好的问题示例，它也很自然地使用递归方法。Quicksort 算法是英国计算机科学家 Tony Hoare 于1959年开发的一种高效排序算法。

Quicksort 是一种分而治之算法。假设有一个待排序的列表。首先从列表中选出一项，称之为基准（pivot），它可以是列表中的任意一项。然后，根据基准，将列表分区（partition），划分为比基准小和比基准大两部分，即得到了两个子列表。再对子列表递归排序。具体算法步骤如下：

选择基准。
根据基准，将列表划分为两个子列表：
1. 子列表1：小于基准的项组成
2. 子列表2：大于基准的项组成
以递归方法，对子列表进行实施 Quicksort 排序。

每次分区都会产生更小的子列表，所以该算法是简化法。基本时间发生在子列表为空或只有一个元素时，因为这些元素本身是有序的。

选择基准

无论以列表中的哪一项为基准，Quicksort 算法都能执行，但有些选择比另一些要好。请记住，在分区时，会创建两个子列表：一个子列表中的项小于基准，另一个子列表中的项大于基准。理想情况下，两个子列表的长度大致相等。

假设要排序的初始列表包含八项。如果每个分区都会产生长度大致相等的子列表，则可以通过三个步骤达到终止条件（如下图所示）。

最优分区示意图

另一方面，如果选择的基准特别不走运，则每个分区产生的两个子列表中，其中一个子列表包含基准以外的所有原始项，另一个子列表为空。在这种情况下，需要七个步骤才能将列表简化为终止条件：

次优分区示意图

在第一种情况下，Quicksort 算法将更有效。但是，为了从全局着手选择最佳基准项，需要提前了解用于排序的数据的特点。在任何情况下，没有任何一个选择对所有情况都是最好的。因此，如果要编写一个 Quicksort 函数来处理一般情况，那么基准的选择就有点随意了。

如果列表中的数据是随机分布的，那么以第一项与最后一项为基准是常见的选择。然而，如果数据已经被排序，或者几乎被排序了，这种方法将导致像上面所示的次优分区。为了避免这种情况，一些 Quicksort 算法选择列表中的中间项作为基准。

另一个做法是找到列表中第一项、最后一项和中间项的中位数，并将其用作基准，这是下面的示例代码中所用的策略。

实现分区

一旦选择了基准，下一步就是对列表进行分区。同样，目标是创建两个子列表，一个子列表包含小于透视项的项，另一个子列表包含大于透视项的项。

你可以直接在原有列表上完成。换言之，通过对列表成员项进行交换，打乱列表中的项的次序，直到基准项位于中间，所有小于它的项位于其左侧，所有大于它的项位于其右侧。然后，运用递归算法对子列表进行 Quicksort 排序，就会将列表的切片传递到基准项的左侧和右侧。

或者，你可以使用 Python 的列表的方法来创建新的列表，而不是在原来的列表上进行操作。这是下面代码中采用的方法。算法如下：

以第一项、最后一项和中间项的中位数（中值）作为所选定的基准。
通过基准创建三个子列表：
1. 子列表1的成员是原始列表中小于基准的项
2. 子列表2是由基准项本身构成
3. 子列表3的成员是原始列表中大于基准的项
对子列表1和子列表3分布进行递归式 Quicksort 。
将所有三个列表重新连接在一起。

请注意，这里创建了一个仅含有基准的子列表，这种方法的一个优点是，它可以顺利地处理基准项多次出现在列表中的情况。在这种情况下，子列表2将有多个元素。

实现 Quicksort

现在基础工作已经就绪，就可以编写 Quicksort 算法的代码了。

import statistics

def quicksort(numbers):
    if len(numbers) <= 1:
        return numbers
    else:
        pivot = statistics.median(
            [
                numbers[0],
                numbers[len(numbers) // 2],
                numbers[-1]
            ]
        )
        items_less, pivot_items, items_greater = (
            [n for n in numbers if n < pivot],
            [n for n in numbers if n == pivot],
            [n for n in numbers if n > pivot]
        )

        return (
            quicksort(items_less) +
            pivot_items +
            quicksort(items_greater)
        )

以下对 quicksort() 做必要的解释：

第4行：列表为空或只有一个元素的终止条件
第7行至第13行：用三个数的中位数（中值）计算基准项
第14行到第18行：创建表示三个分区的列表
第20至24行：分区列表的递归排序和重新组合

注：这个例子的优点是简洁易懂。然而，它并不是最有效的实现。特别是：在第14行到第18行创建分区的部分，需要对列表进行三次独立的循环。从执行时间的角度来看，这不是最佳方案。

下面是调用 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]