Return function in recursion

Question

Understanding the use of return statement in recursion

For example in Binary Search:

def binary_search_recur(array,start,end,item):

    middle = int((start+end)/2)
    #print (middle)
    if (start>end):
        return -1
    else:   
        if array[middle]==item:
            return middle
        elif array[middle]>item:
            return binary_search_recur(array,start,middle-1,item)
        else:
            return binary_search_recur(array,middle+1,end,item)

Calling the function with

array = [27,45,76,81,92,101,291]
binary_search_recur(array,0,len(array)-1,27)

Works fine if I add return statement everywhere, but it does not return 0 (the index of the searched element in the example) if I remove the return statement like below

else:   
      if array[middle]==item:
           return middle
      elif array[middle]>item:
           binary_search_recur(array,start,middle-1,item) #retrun statement removed
      else:
           binary_search_recur(array,middle+1,end,item)   #retrun statement removed

My point is, i would want to return when I find the element so I return the index middle, or if the element is not present at all so in that case I return -1, otherwise I am just calling the function recursively with updated start and end index, Just like merge sort

merge_sort(l)
merge_sort(r)
merge(l,r,array)

So I dont understand why removing the return statement like in the example does not return the op. Any suggestions would be great.

Answer 1

There's nothing special to recursion - it's just plain functions calls and the fact that the function is calling itself is actually totally irrelevant -, and return works just the same as everywhere else.

Consider this:

def a(arg):
    return arg +1 

def b(arg):
    return a(arg * 2)

def main():
    result = b(42)
    print(result)

If you remove the return in b ie:

def b(arg):
    a(arg * 2)

then technically what you actually wrote is:

def b(arg):
    a(arg * 2)
    return None

since when they end up without an explicit return statement, Python functions implicitely return None. And as a result, in main(), result will be None instead of (arg * 2) + 1

It's the exact same thing happening in your code - if you don't explicitely return the result of the recursive call (=> once again, the fact it's a recursive call is technically totally irrelevant, it works exactly the same way), your function will return None, just has if you wrote:

    elif array[middle]>item:
        binary_search_recur(array,start,middle-1,item)
        return None
    else:
        binary_search_recur(array,middle+1,end,item)
        return None