CODEWITHSUNDEEP
pythonalgorithmrecursioninsertion-sort
ariamis07
ariamis07

Reputation: 13

Maximum recursion depth exceeded in my comparison

I am currently reading the Introduction to Algorithms (CLRS). While trying to solve exercise 2.3-4 which is to write insertion sort of A by recursively sorting A[:n-1]. I have written a code for that which i will show below where I generated a list of random numbers and tried to sort it, and it works for up to a certain number of items in the list but when i bumped it up to a thousand I get an error saying maximum recursion depth exceeded in comparison, from checking online I noticed there is a way to increase recursion depth to a certain value, but I am not sure if that is good practice or I should improve my code in some way. Any help would be appreciated. Thank You 

import random
numlist = []
for i in range(1000):
    numlist.append(i)
random.shuffle(numlist)

def rec_ins_sort(L):
    if(len(L) == 1):
        return L
    else:
        step = rec_ins_sort(L[:len(L)-1])
        return insert(L[len(L)-1], step)

def insert(a, inp_list):
    inp_list.append(a)
    i = len(inp_list) - 2
    while(i > 0 and inp_list[i] > a):
        inp_list[i+1] = inp_list[i]
        i -= 1
    inp_list[i+1] = a
    return inp_list

Upvotes: 1

Views: 557

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477200

but I am not sure if that is good practice or I should improve my code in some way.

Algorithms that recurse linear (or superlinear) in the size of the input are usually not a good idea, except if the programming language supports tail call optimization (TCO) (Python does not) and the program is tail recursive. In which case the call stack simply does not grow because the last call frame is overwritten.

MergeSort for instance is an algorithm that recurses in O(log n) with n the size of the input. As a result the call stack does not grow much: if the list has 1'073'741'824 elements, the call stack will grow ~30 levels deep.

For insertion sort. I do not really see an elegant way to let it recurse in O(log n), so you better do not use recursion at all: you can simply use iteration here:

def rec_ins_sort(L):
    iflen(L) < 1:
        return L
    else:
        R = []
        for l in L:
            R = insert(l,R)
        return R

def insert(a, inp_list):
    inp_list.append(a)
    i = len(inp_list) - 2
    while(i > 0 and inp_list[i] > a):
        inp_list[i+1] = inp_list[i]
        i -= 1
    inp_list[i+1] = a
    return inp_list

That being said constructing new lists, etc. is not very efficient either making this algorithm slower than strictly necessary.

So to summarize: you better do not construct algorithms in Python that recurse (super)linear in the size of the input. In that case you better aim to convert it to an iterative approach.

Upvotes: 1

Related Questions