Could someone explain why this fixes my recursion error?

Question

I was implementing binary search recursively in Python (I know this is bad) and got a max recursion error with the following code:

def bs_h(items,key,lower,upper):
    if lower == upper:
        return None
    mid = (lower + upper) // 2
    if key < items[mid]:
        return bs_h(items,key, lower, mid)
    else:
        return bs_h(items,key,mid,upper)

def bs(items,key):
    return bs_h(items,key, 0, len(items)-1)

I then changed my parameters and base case like so:

def bs_h(items,key,lower,upper):
    if lower + 1 == upper:
        return None
    mid = (lower + upper) // 2
    if key < items[mid]:
        return bs_h(items,key, lower, mid)
    else:
        return bs_h(items,key,mid,upper)

def bs(items,key):
    return bs_h(items,key, -1, len(items))

This fixes the error, but I am not sure why. Can someone please explain?

Answer 1

Whenever you use recursion (and it is sometimes very useful), you need to be extremely careful about the end conditions.

1. Does it ever terminate?
2. If it does, how deep will it go?

At some point during the running of your code, you might have a call like:

bs_h(items, key, 10, 11)

which then leads to:

mid = (lower + upper) // 2
    = (10 + 11) // 2
    = 10
if key < items[10]:
    return bs_h(items, key, 10, 10)
else:
    return bs_h(items, key, 10, 11)

Notice that last statement - it's the same as the entry call. If the program ends up at this point, it'll always act recursively.

Always check how you'll escape from recursion, and btw, check your "new improved version" for this.

Answer 2

What fixes your code is this change:

if lower + 1 == upper:
    return None

The change in bs is irrelevant (at least for this purpose; I would actually argue against it).

The reason can be observed from the following experimentation:

>>> (0+0)//2
0

>>> (0+1)//2
0

So, the midpoint does not change once the interval is <= 1 so it follows you should stop at the earliest opportunity, otherwise you will continue looping waiting for midpoint to change which will never occur.

Answer 3

Put a print(lower, upper, mid) statement after your mid = (lower + upper) // 2 statement in your first bs_h example and observe the following:

>>> bs(list(range(10)), 5)
0 9 4
4 9 6
4 6 5
5 6 5
5 6 5
... # repeats until max recursion depth.

Since both (n+n)//2 and (n+n+1)//2 are always the same, you get to a point where you continuously call bs_h with the same lower and upper parameters. You should adjust your subsequent calls to eliminate the boundary conditions (which have already been checked). You also need to return something like the index. The following matches the recursion pattern you want and returns the correct index:

def bs_h(items,key,lower,upper):
    if lower > upper:
        return None
    mid = (lower + upper) // 2
    if key < items[mid]:
        return bs_h(items,key, lower, mid-1)
    elif key > items[mid]:
        return bs_h(items,key,mid+1,upper)
    else:
        return mid #Found! return index

And tested:

>>> for i in range(10):
    print(bs(list(range(10)), i))

0
1
2
3
4
5
6
7
8
9

>>> print(bs(list(range(10)), 4.5))
None

>>> print(bs(list(range(10)), 100000))
None

Answer 4

Glenn Rogeres got it right. But to make sure things aren't missed,

• Firstly, its binary search - which means to find a value in a sorted list.
• you can return the index of the element(in your case, mid variable once the element is found!)
• after checking if the key is < or > than the items[mid] you can ignore the mid element in your next recursive search(mid-1 or mid+1)

That is,

def bs_h(items,key,lower,upper):
    if lower>upper:return None
    mid = (lower + upper )// 2
    if key < items[mid]:
        return bs_h(items,key, lower, mid-1) 
    elif key > items[mid]:
        return bs_h(items,key, mid+1, upper)
    else:return mid

def bs(items,key):
    return bs_h(sorted(items),key, 0, len(items)-1)