Recursive way of Binary Search with nested function in Python

Question

I implemented a recursive way of binary search and I'm facing a problem. Ths is my code:

def foo(x, ls):
    left, right = 0, len(ls)-1
    def search(l, r):
        if l>r:
            return False
        mid = (l+r)//2
        if x < ls[mid]:
            return search(l,mid-1)
        elif x > ls[mid]:
            return search(mid+1,r)
        else:
            return True

    return search(left,right)

this function works fine. However if I remove the return from the if statements, and call search function without a return, it raises wrong answers. Can anyone explain this? What is the exact difference?

I don't get what you're asking. You created a code that works, and you wonder why breaking it doesn't work? — Ofer Sadan, Dec 07 '19 at 15:43
No, i dont wanna break it. I just asking the diference between recursing with return statement and without. — KoZark, Dec 07 '19 at 15:45
Because without `return` you're running the same code but the calculation being done just disappears when it's done. `return` does just that, it returns the result you worked hard to get. — Ofer Sadan, Dec 07 '19 at 15:49

Yoni Mantzur · Accepted Answer · 2019-12-07T16:17:04.770

1

If you don't return a value in a recursive function, the tail of this function is just returning None, which is evaluated to False if you try to convert it to boolean value

edited Dec 07 '19 at 16:17

answered Dec 07 '19 at 16:00

Yoni Mantzur

42
8

Recursive way of Binary Search with nested function in Python

1 Answers1