Recursive binary search in Python hits the recursion ceiling

Question

So I'm writing a recursive binary search algorithim in Python and it's been working great ...... except when I tried a certain number.

I'm working off of a list of 10,000 randomized numbers that have been sorted.

It eventually fails with this error:

RecursionError: maximum recursion depth exceeded while calling a Python object

I've put in counters inside the function to keep track of the low/high points and current search count. When I run bSearch(3333), I get the above error and this weird output...

It just keeps repeating 338 337 until it reaches the cursions ceiling.

Here's my function:

def bSearch(list, value, lowPoint=0, highPoint=None, searchNum=1):
    print(lowPoint,highPoint,searchNum)
    searchNum += 1
    if highPoint is None:
        highPoint = len(list) - 1
    if lowPoint == highPoint:
        if list[lowPoint] == value:
            return lowPoint, searchNum
        else:
            return -1, searchNum
    midPoint = (lowPoint + highPoint) // 2
    if list[midPoint] > value:
        return bSearch(list, value, lowPoint, midPoint - 1, searchNum)
    elif list[midPoint] < value:
        return bSearch(list, value, midPoint + 1, highPoint, searchNum)
    else:
        return midPoint

gman · Accepted Answer · 2015-11-05 19:01:50Z

1

The reason is you haven't handled one terminating condition. when your lower limit is higher than your higher limit, This means the element you are searching is not there in the list you should return a -1 there.

def bSearch(list, value, lowPoint=0, highPoint=None, searchNum=1):
    print(lowPoint,highPoint,searchNum)
    searchNum += 1
    if highPoint is None:
        highPoint = len(list) - 1
    if lowPoint == highPoint:
        if list[lowPoint] == value:
            return lowPoint, searchNum
        else:
            return -1, searchNum
    if lowPoint > highPoint:
        return -1,searchNum
    midPoint = (lowPoint + highPoint) // 2
    if list[midPoint] > value:
        return bSearch(list, value, lowPoint, midPoint - 1, searchNum)
    elif list[midPoint] < value:
        return bSearch(list, value, midPoint + 1, highPoint, searchNum)
    else:
        return midPoint

answered Nov 5, 2015 at 19:01

gman

1,2722 gold badges16 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Zeratas Over a year ago

-__- Should have thought the terminating conditions through more! Thanks!

Zeratas Over a year ago

I also just combined the two like this: if lowPoint >= highPoint:

gman Over a year ago

Yeah that makes sense \m/

Collectives™ on Stack Overflow

Recursive binary search in Python hits the recursion ceiling

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related