I have a recursion limit error in my quick sort program although I set recursion limit to 1500

Question

I am trying to write an in-place program that would use the quicksort algorithm to sort a list. But it keeps giving an error:

maximum recursion depth exceeded while calling python object.

Although I tried setting recursion limit.

def partition(L,low,high,comparison):
    i=low-1
    pivot=random_pivot(L)
    for j in range(low,high):
        if comparison(L[j],pivot):
            i+=1
            L[i],L[j]=L[j],L[i]
    L[i+1],L[high]=L[high],L[i+1]
    return i+1
def inplace_Quicksort(L,low,high,comparison):
    low=0
    high=len(L)-1
    if comparison(low,high):
        pivot_index=partition(L,low,high,comparison)
        inplace_Quicksort(L,low,pivot_index-1,comparison)
        inplace_Quicksort(L,pivot_index+1,high,comparison)
    print(L)

Can you please have a look at it and explain to me what is wrong? Thank you so much.

Try to debug your code yourself to see why the code recurses infinitely many times. — user202729, Nov 10 '18 at 16:16
Please be so good to not destroy the constructive edits made by others. — trincot, Nov 10 '18 at 16:16
What is `random_pivot`, and why do the arguments involve no range information? — user2357112, Nov 10 '18 at 16:17

score 1 · Answer 1 · answered Nov 10 '18 at 16:18

You are resetting the range to the complete list each time you call inplace_Quicksort in the first two lines of its code, thereby making the arguments low and high useless.

This leads to an endless recursion. No increase of maximum recursion depth will help you.

Instead give your arguments a default value. Look how it is done in this answer.

I have a recursion limit error in my quick sort program although I set recursion limit to 1500

1 Answers1