最大递归深度错误，以某种方式与列表理解符号相关(Maximum recursion depth error, somehow related to list comprehension notatio

最大递归深度错误，以某种方式与列表理解符号相关(Maximum recursion depth error, somehow related to list comprehension notation)

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

作为速成课程的一部分，我使用列表quicksort编写了一个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[1:]而不是lst

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

I'm completely new to Python and I'm stumped by the following.

As part of a crash course, I've written a quicksort function using list comprehensions, as follows:

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

This results in the following output:

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

Yet the following works fine:

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

The only difference is lst[1:] instead of lst

Documentation on list comprehensions did not seem to address this.

最满意答案

您永远不会在第一个片段中更改主元，所以lessThanPivot的“小于”分区再次少于lessThanPivot （即等效列表），而greaterThanPivot的“大于”分区再次大于greaterThanPivot ，从而导致无限递归。

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

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

You are never changing your pivot in the first snippet, so the "less-than" partition of lessThanPivot is again lessThanPivot (i.e. an equivalent list) and the "greater-than" partition of greaterThanPivot is again greaterThanPivot, leading to an infinite recursion.

Your second snippet "works" because lst[1:] keeps trimming off the first element of the list, so the list gets smaller with each recurrence, eventually leading to the base case. The final answer is incorrect, however.

In short, pick a new pivot before each partition.