CODEWITHSUNDEEP
pythonsortingrecursion
smith
smith

Reputation: 379

can't understand why I'm getting maximum recursion depth here

I have such function:

def sort(lst, beg, end):
    mid = (beg + end)/2
    sort(lst, beg, mid)
    sort(lst, mid, end)
    i = 0
    j = 0
    for l in range(beg, end):
        if j > end - mid or (i <= mid - beg and lst[beg + i] < lst[mid + j]):
            lst[l] = lst[beg + i]
            i = i + 1
        else:
            lst[l] = lst[mid + j]
            j = j + 1

Input is : sort([1,5,6,6,3,1,5,4,3,3,4,5,6,7,8,5,3,2,4,5], 1, 10)

as output: 

RuntimeError: maximum recursion depth exceeded

How can I fix this?

Upvotes: 0

Views: 135

Answers (2)

Biniou
Biniou

Reputation: 133

There is nothing preventing the recursion. Every time sort is called, it will call itself 2 times. There should be a conditional statement.

Upvotes: 3

Mureinik
Mureinik

Reputation: 311843

You are missing a condition that will stop you from recursing. In the current implementation, you will just continue indefinitely.

e.g.:

def sort(lst, beg, end):
    if end - beg <= 1:
        return

    mid = (beg + end)/2
    sort(lst, beg, mid)
    sort(lst, mid, end)
    # rest of code

Upvotes: 5

Related Questions