Maximum recursion depth error, somehow related to list comprehension notation

Question

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. The only difference is lst[1:] instead of lst.

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)

Documentation on list comprehensions did not seem to address this.

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