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?

score 6 · Accepted Answer · answered Jul 31 '15 at 07:03

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.

Recursive function returning none?

1 Answers1

Linked