CODEWITHSUNDEEP
pythonarrayslistsortingbinary-search
Blem.Hamza
Blem.Hamza

Reputation: 1

Why i am having a maximum recursion depth exceeded error

I am trying to apply the Binary Search algorithm (the recursive way) and I'm having this error

def BinarySearchRec(tab, x):
    mid = len(tab) // 2
    if len(tab) == 0:
        return False
    if tab[mid] > x:
        return BinarySearchRec(tab[:mid], x)
    elif tab[mid] < x:
        return BinarySearchRec(tab[mid:], x)
    else:
        return mid

I tried to 1 and retrive one when i call the function back but didn't work on all cases

Upvotes: -4

Views: 252

Answers (1)

C-3PO
C-3PO

Reputation: 1213

When mid=0 and tab[mid] < x, the code gets stuck because BinarySearchRec(tab[mid:], x) will loop forever with the same inputs: (tab[mid:],x) -> (tab[0:],x) -> (tab,x) .

As a proof, you can try the following example:

tab = [1]
x   = 2
BinarySearchRec(tab, x)
# recursion error raised

The easiest solution is to make sure that the array tab decreases in size every time you perform recursion:

def BinarySearchRec(tab, x, i=0, j=None):
    # edit: added (i,j) bounds, instead of array slices tab[a:b]
    #       this is much faster, and lowers the time complexity
    #       per recursion to O(1) instead of O(n)
    if j is None: j = len(tab)-1
    mid = (i+j)//2
    if j < i:
        return False
    elif tab[mid] == x:
        return mid
    elif x < tab[mid]:
        return BinarySearchRec(tab, x, i, mid-1)
    elif tab[mid] < x:
        return BinarySearchRec(tab, x, mid+1, j)

tab = [1]
x   = 2
BinarySearchRec(tab, x)
# now it works

In the new code, the tab array is trimmed using either mid+1 or mid-1, since we can discard mid as a solution when tab[mid] != x. This makes sure that tab always decreases at least one element in size, and hence the code does not crash. Cheers,

Function testing:

assert BinarySearchRec([1,2,3],-1) == False # ok
assert BinarySearchRec([1,2,3], 1) == 0     # ok
assert BinarySearchRec([1,2,3], 2) == 1     # ok
assert BinarySearchRec([1,2,3], 3) == 2     # ok
assert BinarySearchRec([1,2,3], 4) == False # ok

Upvotes: 1

Related Questions