Segmentation Fault when running recursive binary search algorithm

Question

So I'm trying recursion for the first time, writing a simple binary search algorithm in Python 3. After running my program I was getting this error: maximum recursion depth exceeded while calling a Python object I did some research and it said to add this line: sys.setrecursionlimit(40000)

Which I did. When I enter a number that's not in my list I get this Segmentation Fault error. I read this post From what I gather in Python deep recursion exhausts the memory?

I can't imagine deep recursion is not supported in Python? Anyways, here's my code:

import sys

arr = [5, 17, 23, 33, 39, 44, 58, 62, 70, 74, 82, 99]
end = len(arr)
sys.setrecursionlimit(40000)

def binarySearch(arr, start, end,  x):

   #print("This is end: {}".format(end))
    mid = int((end + start)/2)
    #print("This is start {}".format(start))
    #print("This is end {}".format(end))
    #print("This is mid {}".format(mid))

    if x == arr[mid]:
        return x
    elif (x < arr[mid]):
        start = 0
        end = mid - 1
        return binarySearch(arr, start, end, x)
    else: # if x > arr[mid]
        start = mid + 1
        end = end
        return binarySearch(arr, start, end,  x)


position = binarySearch(arr, 0, 12, 55)
print(position)

There is no way you'd need that many recursive calls using binary search. There's no array that big that can fit into memory. — cs95
– cs95, Commented Feb 3, 2018 at 2:57
I haven't gone over your code yet, but if you're getting a recursion error on a data structure this small, your algorithm is doing something wrong. (Generally getting a recursion error tells you you did something wrong, or your problem is not a recursive problem, and shouldn't have a recursive solution) — Patrick Haugh
– Patrick Haugh, Commented Feb 3, 2018 at 2:57
Your code makes no provision for x not being in arr. What would you expect it to return in that case? (Also, you should probably be returning mid not x) — Patrick Haugh
– Patrick Haugh, Commented Feb 3, 2018 at 3:00
You have a few mistakes here. start = 0 is one of them. Another is that you don't check for the base case start > end. — cs95
– cs95, Commented Feb 3, 2018 at 3:01
"I can't imagine deep recursion is not supported in Python?" - deep recursion is most certainly supported in Python, but infinite memory is not. Even if you set the maximum recursion level to a large number, the interpreter can still run out of memory. — Chris
– Chris, Commented Feb 3, 2018 at 3:06

cs95 · Accepted Answer · 2018-02-03 03:06:56Z

5

You have a couple of mistakes in your code:

You don't have a base case. You're supposed to check whether start > end before going through with the recursion.
start = 0 really should be start = start, or don't add it at all.

Fixing these bugs, and cleaning up your code a bit, this works -

def binarySearch(arr, start, end, x):
    if start <= end:
        mid = (end + start) // 2

        if x == arr[mid]:
            return mid
        elif x < arr[mid]:
            end = mid - 1           
        else:
            start = mid + 1

        return binarySearch(arr, start, end, x)

    return -1

binarySearch(arr, 0, len(arr), 55)
-1

binarySearch(arr, 0, len(arr), 58)
6

Also, note that, for a O(logN) algorithm, you'll never need a maximum recursion depth of 40,000. If you're running into a "maximum recursion depth exceeded" error, you should re-evaluate your algorithm first.

edited Feb 3, 2018 at 3:06

answered Feb 3, 2018 at 3:03

cs95

406k106 gold badges744 silver badges797 bronze badges

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

2 Comments

cs95 Over a year ago

@ChristianDean Thank you, you too. This week has been a bit busy for me :)

cs95 Over a year ago

@newcoder Welcome! Always remember to check your base case(s) when writing recursive routines.

Collectives™ on Stack Overflow

Segmentation Fault when running recursive binary search algorithm

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related