最大递归深度误差，与列表理解符号有某种关系

Question

我是 Python 的新手，我对以下内容感到困惑。

作为速成课程的一部分，我使用列表理解编写了一个 quicksort 函数，如下所示：

data = [78,3,3526,-12244,9,2,8,6,-84,3642,1,-1234, 234, 23, -1, -11, 34]
pivot = data[0]

def quicksort(lst):
    if len(lst) <= 1:
        return lst
    lessThanPivot = [x for x in lst if x < pivot]
    greaterThanPivot = [x for x in lst if x >= pivot]
    return quicksort(lessThanPivot) + [pivot] + quicksort(greaterThanPivot)

print(quicksort(data))

这导致以下输出：

Traceback (most recent call last):
File "C:\Program Files (x86)\Microsoft Visual Studio 12.0\Common7\IDE\Extensions\Microsoft\Python Tools for Visual Studio.1\visualstudio_py_util.py", line 106, in exec_file
exec_code(code, file, global_variables)
File "C:\Program Files (x86)\Microsoft Visual Studio 12.0\Common7\IDE\Extensions\Microsoft\Python Tools for Visual Studio.1\visualstudio_py_util.py", line 82, in exec_code
exec(code_obj, global_variables)
File "C:\Users\user\documents\visual studio 2013\Projects\PythonApplication1\PythonApplication1\quickSortExercise.py", line 12, in <module>
print(quicksort(data))
[...]
File "C:\Users\user\documents\visual studio 2013\Projects\PythonApplication1\PythonApplication1\quickSortExercise.py", line 3, in quicksort
def quicksort(lst):
RuntimeError: maximum recursion depth exceeded

但以下工作正常：

data = [78,3,3526,-12244,9,2,8,6,-84,3642,1,-1234, 234, 23, -1, -11, 34]
pivot = data[0]

def quicksort(lst):
    if len(lst) <= 1:
        return lst
    lessThanPivot = [x for x in lst[1:] if x < pivot]
    greaterThanPivot = [x for x in lst[1:] if x >= pivot]
    return quicksort(lessThanPivot) + [pivot] + quicksort(greaterThanPivot)
print(quicksort(data))

唯一的区别是 lst[1:] 而不是 lst

关于列表理解的文档似乎没有解决这个问题。

Answer 1

您永远不会更改第一个代码段中的主元，因此 lessThanPivot 的 "less-than" 分区又是 lessThanPivot（即等效列表）和 "greater-than" greaterThanPivot 的划分又是 greaterThanPivot，导致无限递归。

您的第二个代码段 "works" 因为 lst[1:] 不断删减列表的第一个元素，所以每次重复时列表都会变小，最终导致基本情况。然而，最终答案是错误的。

简而言之，在每个分区之前选择一个新的主元。

Answer 2

somelist[1:] 使用切片表示法生成一个列表，其中包含第一个元素之后的所有元素。有关切片符号的解释，请参阅 this question。

第一次排序失败的原因是列表 greaterThanPivot 也始终包含主元，因为主元是第一个元素并且使用的条件是 x >= pivot。因此 greaterThanPivot 上的递归总是包含相同的主元，并且在第一个分区之后永远不会变小。在您的示例中，在第一步 greaterThanPivot = [78, 3526, 3642, 234] 之后，如果您通过算法跟踪它，您将看到它将始终包含该值，直到您运行出栈 space .

在第二种算法中，切片符号用于删除列表的第一个元素，即在分区之前删除主元。这防止了包含枢轴的列表上的无限递归。

最大递归深度误差，与列表理解符号有某种关系

Maximum recursion depth error, somehow related to list comprehension notation

python

recursion

runtime-error

list-comprehension