递归深度达到最大值错误，与列表推导符号相关

Question

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

作为速成课程的一部分，我使用列表推导式编写了一个快速排序函数，如下所示：

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\2.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\2.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替换为lst[1:] 列表推导式的文档似乎没有涉及到这个问题。

- Blorbstein

---

唯一的区别是 lst[1:] 而不是 lst。这是一个很大的区别。前者将使用越来越小的列表子集调用函数。而后者会导致无限递归。 - Cory Kramer

注意：要插入内联代码，请使用反引号。当您想提供错误消息时，应该1）将它们格式化为代码2）复制所有输出，从行Traceback（most recent call last）：到行ErrorName：message，而不仅仅是最后一行。 - Bakuriu

@Cyber - 你能详细解释一下吗？我认为lst会产生相同的结果，因为lessThanPivot本质上是一个比lst小的列表，并且在其中递归调用quicksort。 - Blorbstein

@Bakuriu - 谢谢，不过整个输出结果非常冗长和重复，所以我倾向于在这种情况下省略部分内容。 - Blorbstein

@Blorbstein 如果你有同样的代码行重复了1000次，只需放几个，然后用省略号 [...] 表示其余部分。关键是：也许 你 无法理解它们所传达的信息，但对于 我们 来说，它们非常有用，可以帮助我们了解出了什么问题，特别是在无法提供完整代码的情况下。 - Bakuriu

Answer 1

在第一个代码段中，您从未改变枢轴，因此“小于”lessThanPivot的分区仍然是lessThanPivot（即等效列表），而greaterThanPivot的“大于”分区仍然是greaterThanPivot，导致无限递归。

在第二个代码段中，lst[1:]一直在修剪列表的第一个元素，因此每次递归时列表都会变得更小，最终导致基本情况。但是，最终答案是不正确的。

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

- arshajii

---

哦，我的天啊，这太傻了。非常感谢！/尴尬 - Blorbstein

Answer 2

somelist[1:]使用切片符号产生一个列表，其中包含第一个元素后的所有元素。关于切片符号的解释，请参考这个问题。

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

在第二个算法中，使用切片符号删除列表的第一个元素，也就是在分区之前删除枢轴。这样可以防止包含枢轴的列表出现无限递归。

- zstewart