CODEWITHSUNDEEP
pythonrecursion
martin
martin

Reputation: 1185

How to handle with recursion error in python?

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?

Upvotes: 2

Views: 611

Answers (1)

trincot
trincot

Reputation: 350310

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.

Upvotes: 2

Related Questions