How to handle with recursion error in python?

Question

First, I create 6 lists of random numbers, where each list has a different length:

arr = [random.randint(1,15000) for _ in range(1000)]

numbersList = [10,100,500,1000,5000,8000]
numbersForBenchmark = []
for i in range(len(numbersList)):
    arr = [random.randint(1,15000) for _ in range(numbersList[i])]
    numbersForBenchmark.append(arr)

print(numbersForBenchmark)
recursionTimeArray = []

Now I have a recursion QuickSort:

def partition(lst, start, end):
    pos = start                           

    for i in range(start, end):           
        if lst[i] < lst[end]:            
            lst[i],lst[pos] = lst[pos],lst[i]
            pos += 1

    lst[pos],lst[end] = lst[end],lst[pos] 
    return pos

def quick_sort_recursive(lst, start, end):
    if start < end:                     
        pos = partition(lst, start, end)
        quick_sort_recursive(lst, start, pos - 1)
        quick_sort_recursive(lst, pos + 1, end)

And then driver working on all of arrays:

for i in range(len(numbersForBenchmark)):
   arrRe = numbersForBenchmark[i]
   try:
        n = len(arrRe)
        start = time.time()
        quick_sort_recursive(arrRe,0,n-1)
        end = time.time()
        rekTime = end - start
        recursionTimeArray.append(rekTime)
   except RecursionError as re:
        print('Problem with recursive depth!)

So as you can see, I measure the time and put the time into an array. But I need 6 results (I have 6 arrays), but in two examples, I got an error two times:

    print('Problem with recursive depth!)

I tried to handle it with:

import sys
sys.setrecursionlimit(1500)

But program finishes somewhere in midde, and I don't get any results.

How Can I fix this?

Generally speaking, if you hit the recursion limit it's because you've made an error somewhere and are going into infinite recursion. — Michael Bianconi, Jan 31 '20 at 21:50
[this might help](https://stackoverflow.com/questions/59437588/implement-number-of-digits-recursively-in-python), as mentioned if you hit the recursion limit its usually best to implement it iteratively — BpY, Jan 31 '20 at 21:52
OK, thanks for suggestion. But I don't get why for 3 arrayst it's works but for two (seems it's first and 2nd) not. Can u see my mistake? — martin, Jan 31 '20 at 21:53
You might want to verify that `partition` isn't returning `end+1` at some point. — chepner, Jan 31 '20 at 22:01
It's normal that recursive QuickSort is much slower than iterative? — martin, Jan 31 '20 at 22:25
Definitely, for quicksort you shouldn't be adjusting the recursion limit. Generally, you almost *never* should. Note, if you are hitting a recursion limit of 1000, and quicksort requires log2(N) recursive calls, where N is the length of your list. Which implies your list is at least 2**1000 items long... — juanpa.arrivillaga, Jan 31 '20 at 22:31
@martin in Python, recursion is generally slower than an equivalent iterative solution (of course, they have the same complexity, but the constant factors are larger, namely, the cost of the function call, which is relatively steep in python) — juanpa.arrivillaga, Jan 31 '20 at 22:31

score 2 · Accepted Answer · answered Jan 31 '20 at 22:29

Some observations:

Your simplified question leaves out an important aspect that was present in an earlier version of your question: your original code also includes a call of an iterative sorting function
That test is biased, because you first sort the list with the iterative method, and then use the same list -- which is now sorted -- with your quicksort implementation
Your quicksort implementation will get into its worst case when the input list is already sorted. The pos variable will become equal to end, and so the next partitioning will chop off just one value, meaning that your recursion depth will be equal to the number of elements in your list. For larger lists, you'll thus run into the recursion limit.

So, counting on the randomness of your input lists, just solving the first issue should be enough. Replace these lines:

arrIt = numbersForBenchmark[i]
arrRe = numbersForBenchmark[i]

with:

arrIt = numbersForBenchmark[i][:]
arrRe = numbersForBenchmark[i][:]

... and there should be no more problem.

Thank U so much for comprehensive explanations. I change it and it's works fine. Thanks again! So btw it's seems that recursive is faster than iterative in this example. — martin, Jan 31 '20 at 22:38

How to handle with recursion error in python?

1 Answers1