python - Recursive function returning none?

Question

I wrote the following function in order to implement my own binary search

def bisect(input, target):
    mid = len(input)/ 2
    if len(input) == 1:
        if input[0] == target:
            return 1
        else:
            return None
    elif input[mid] > target:
        bisect(input[:mid], target)
    elif input[mid] <= target:
        bisect(input[mid:], target)

I know my implementation is off, but I am more curious in understanding the recursive stack here.

When I call bisect(['d','e'], 'd'), my function should return the value of

bisect(['d'], 'd')

but instead it returns None. Further, when I call bisect(['d'], 'd')directly, I get the correct value of 0. How is this possible?

Answer 1

You are ignoring the return values of recursive calls. You need to explicitly return those too:

elif input[mid] > target:
    return bisect(input[:mid], target)
elif input[mid] <= target:
    return bisect(input[mid:], target)

Recursive calls are just like any other function call; they return a result to the caller. If you ignore the return value and the calling function then ends, you end up with that calling function then returning None instead.