最大递归深度误差，某种程度上与列表理解符号

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

文档似乎并没有解决这个问题。

Answer 1

你永远不会改变的第一个片段的支点，所以“小于”的lessThanPivot分区再次lessThanPivot（即等价列表）和“大于”的greaterThanPivot分区再次greaterThanPivot，导致无限递归。

您的第二个片段“有用”，因为lst[1:]不断修整列表的第一个元素，所以列表随着每次重复而变小，最终导致基本情况。但最终的答案是不正确的。

总之，每个分区之前选择一个新的枢轴。

Answer 2

somelist[1:]使用切片表示法，以产生包含了所有的第一个之后的元素的列表。关于切片符号的解释见this question。

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

在第二算法中，切片表示法被用来删除列表的第一个元素，即，它消除分区之前的枢轴。这可以防止包含该透视的列表上的无限递归。