Recursion and Return Statements

Return Statements in Recursion

Not understanding how recursive functions work is quite common, but it really indicates that you just don't understand how functions and returning works, because recursive functions work exactly the same as ordinary functions.

print 4

This works because the print statement knows how to print values. It is given the value 4, and prints it.

print 3 + 1

The print statement doesn't understand how to print 3 + 1. 3 + 1 is not a value, it's an expression. Fortunately print doesn't need to know how to print an expression, because it never sees it. Python passes values to things, not expressions. So what Python does is evaluate the expression when the code is executed. In this case, that results in the value 4 being produced. Then the value 4 is given to the print statement, which happily prints it.

def f(x):
    return x + 1

print f(3)

This is very similar to the above. f(3) is an expression, not a value. print can't do anything with it. Python has to evaluate the expression to produce a value to give to print. It does that by going and looking up the name f, which fortunately finds the function object created by the def statement, and calling the function with the argument 3.

This results the function's body being executed, with x bound to 3. As in the case with print, the return statement can't do anything with the expression x + 1, so Python evaluates that expression to try to find a value. x + 1 with x bound to 3 produces the value 4, which is then returned.

Returning a value from a function makes the evaluation of the function-call expression become that value. So, back out in print f(3), Python has successfully evaluated the expression f(3) to the value 4. Which print can then print.

def f(x):
    return x + 2

def g(y):
    return f(y * 2)

print g(1)

Here again, g(2) is an expression not a value, so it needs to be evaluated. Evaluating g(2) leads us to f(y * 2) with y bound to 1. y * 2 isn't a value, so we can't call f on it; we'll have to evaluate that first, which produces the value 2. We can then call f on 2, which returns x + 2 with x bound to 2. x + 2 evaluates to the value 4, which is returned from f and becomes the value of the expression f(y * 2) inside g. This finally gives a value for g to return, so the expression g(1) is evaluated to the value 4, which is then printed.

Note that when drilling down to evaluate f(2) Python still "remembered" that it was already in the middle of evaluating g(1), and it comes back to the right place once it knows what f(2) evaluates to.

That's it. That's all there is. You don't need to understand anything special about recursive functions. return makes the expression that called this particular invocation of the function become the value that was given to return. The immediate expression, not some higher-level expression that called a function that called a function that called a function. The innermost one. It doesn't matter whether the intermediate function-calls happen to be to the same function as this one or not. There's no way for return to even know whether this function was invoked recursively or not, let alone behave differently in the two cases. return always always always returns its value to the direct caller of this function, whatever it is. It never never never "skips" any of those steps and returns the value to a caller further out (such as the outermost caller of a recursive function).

But to help you see that this works, lets trace through the evaluation of fib(3) in more detail.

fib(3):
    3 is not equal to 0 or equal to 1
    need to evaluate fib(3 - 1) + fib(3 - 2)
        3 - 1 is 2
        fib(2):
            2 is not equal to 0 or equal to 1
            need to evaluate fib(2 - 1) + fib(2 - 2)
                2 - 1 is 1
                fib(1):
                    1 is equal to 0 or equal to 1
                    return 1
                fib(1) is 1
                2 - 2  is 0
                fib(0):
                    0 is equal to 0 or equal to 1
                    return 1
                fib(0) is 1
            so fib(2 - 1) + fib(2 - 2) is 1 + 1
        fib(2) is 2
        3 - 2 is 1
        fib(1):
            1 is equal to 0 or equal to 1
            return 1
        fib(1) is 1
    so fib(3 - 1) + fib(3 - 2) is 2 + 1
fib(3) is 3

More succinctly, fib(3) returns fib(2) + fib(1). fib(1) returns 1, but fib(3) returns that plus the result of fib(2). fib(2) returns fib(1) + fib(0); both of those return 1, so adding them together gives fib(2) the result of 2. Coming back to fib(3), which was fib(2) + fib(1), we're now in a position to say that that is 2 + 1 which is 3.

The key point you were missing was that while fib(0) or fib(1) returns 1, those 1s form part of the expressions that higher level calls are adding up.

Return function in recursion

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

How does the return statement work in recursion?

Well, when you are specifying the return type of a function, the function indeed expected to return some value when the control-flow left out from the function.

so a function, int function() is expected to return a value of type integer, that's the standard.

Now, coming to your program, you have divided the array into two halves, and again in two halves from one of the halve created by the previous call, and continuously you are doing so, until and unless either you have found the value or you have exhausted all halves (which are valid, in terms of binary search).

Let's understand it thoroughly:

    Let's say you have an array {1, 2, 3, 4, 5, 6, 7} and key {2}

so in terms of binary search, since the middle of the array which is 4 is the not element you are looking for, you would split the array into two halves and you would consider the left subarray since the middle{4} was greater than the element you are searching:

         left_sub_array = {1,2,3,4} and right_sub_array = {5, 6, 7}

Again you would do the same thing, and you would stop and return the key/index, because:

since the middle of the current subarray {1,2,3,4} is 2, is the value you are looking for{2}. 

Let's follow the control-flow again,

         *first instance*
         | int binarysearch(int * array, int arrlen, int key ){
         |      ...split the array by middle index and call second instance of the function "binarysearch"
         | }
                
              *second instance*
              | int binarysearch(int * array, int arrlen, int key){
              | ... got the element and return the value to first instance of the function "binarysearch"
              |}

so you can now understand, for every self-call, we are creating an instance of the function and return a value (either result or not a result) when we got the result or come into the base condition.

The same thing is happening in your code too:

if(a[mid] < x){
    return binarySearch(a, size, x, mid+1, high);
}
else{
    return binarySearch(a, size, x, low, mid-1);
}

but to understand it better, let's store the value of the returned result into a variable and return the variable at the time of success (when key is found) or failure (when base case reached, key is not found).

int binarySearch(int a[], int size, int x, int low, int high){
   int result = -1;
   if(low > high) return -1;

   int mid = (low + high)/2;

   if(a[mid] == x){
    return mid;
   }

   if(a[mid] < x){
      result = binarySearch(a, size, x, mid+1, high);
   }
   else{
      result = binarySearch(a, size, x, low, mid-1);
   }
   return result;
}

So you can see we are creating a variable result for each instance of the function and store the returned value of the next instance into the variable, and continue doing so till the end (success/failure) and return the variable.

Why doesn't return statement end a recursive function in c?

Each recursive call the function has a return value, returning on a call later on does not jump out of the recursion to main, it just jumps out to the previous call. This is how it can reach multiple return statements.

As each call resolves on the stack, the function will complete through the rest of the code, this is how we reach code that comes after the recursive call (in f_b)

If I'm not mistaken, this function returns the smallest value in the array.

---

Related Topics