Function call to self with return statement works ...but why?

Question

I am trying to get my head around Python having only really ever coded in Java in the past. I need some help understanding some code if someone can help, or point me in the direction of a good (simple) resource please?

I have written a Binary sort in Python from some pseudocode, it works but I don't understand how. The function would make sense to me if the code below didn't have a return statement on the line:

return findData( data, criteria, first, mid -1 ) 

Or if I set up a while loop and just modified the start or end index variable based on which half of the list I needed to reference.

But with this code I don't understand where the function is being returned to, or why the code fails if i remove them?? It makes sense that I return -1 as no match and 'mid' to reference the list position of a match, but the return statement passing data, criteria, first and last should surly cause a syntax error as there is no call to such a function?

Thanks in advance to anyone who can explain how what I have written works. My code is below.

Mr.D

# Binary Search

def findData( data, criteria, first, last ):

    if( last < first ):
        return -1

    else:
        mid = ( last + first ) // 2

        if( criteria == data[mid] ):
            return mid

        elif ( criteria > data[mid] ):
            print( "Currently looking at", data[mid], "in array poition", mid )
            return findData( data, criteria, mid +1, last )

        elif( criteria < data[mid] ):
            print( "Currently looking at", data[mid], "in array poition", mid )
            return findData( data, criteria, first, mid -1 )


Data = [15, 21, 29, 32, 37, 40, 42, 43, 48, 50, 60, 64, 77, 81, 90, 98]
Criteria = 98
Location = -1

Location = findData( Data, Criteria, 0, len( Data ) -1 )

if( Location < 0 ):
    print( Criteria, "is not located in the array." )
else:        
    print( Criteria, "is located in array position ", Location )

Answer 1

This is a recursive function, therefore for the solution to converge to your solution (if it indeed does exist in the list, otherwise the function returns -1) it will need to continually call itself with it's current data, criteria and first (which have not changed since the first call to findData()) and it's new value of last. The new value of last is continually updated inside of the recursive function as either mid+1 or mid-1 until criteria==data[mid], at which point the index of criteria is returned as mid and set to the variable Location.

Answer 2

return -1

This means evaluate the expression -1 and return the result back as the result of this function.

return mid + 1

This means evaluate the expression mid + 1 and return the result back as the result of this function.

return findData( data, criteria, first, mid -1 ) 

This means evaluate the expression findData( data, criteria, first, mid -1 ), which again means call the function findData with the evaluated arguments, and return the result back as the result of this function. This does not return a function. You could actually split it up like this:

Location = findData( data, criteria, first, mid -1 ) 
return Location

This is exactly the same. And the first line is exactly what you do to call the function in the first place.

Now if you call a function and do not use its return value it is dead code. Imagine this code:

def test(n):
  somefun(n)

test(5) # ==> None

Now if you had returned the result of somefun then test would be an alias for somefun.

If you wanted to return a function you would not apply it by using the parens and argument:

return findData    # returns a fucntion by name
return lambda v: v # return a lambda function

And of course. Recursive functions have no magic. As with all functions that call functions it waits for it to return to resume its own execution. The fact that the function that is called happens to be the same doesn't really matter. the bound parameters and local variables will be local to each call and thus they don't leak and each call return to the previous. No magic whatsoever. It could have been different functions that provided the same functionality each time.