How does the return statement work in recursion?

Question

#include<iostream>
using namespace std;

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

    int mid = (low + high)/2;

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

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

int main(){
    int a[] = {1, 2, 3, 4, 5, 6};
    int size = sizeof(a) / sizeof(a[0]);
    cout<<binarySearch(a, size, 5, 0, size-1);
}

For example in this program that performs Binary search using recursion, I am confused in the usage of return keyword in the statement return binarySearch(a, size, x, mid+1, high);.

Ignoring the fact that not writing the return keyword in this statement gives a warning, what will be the difference if i dont write return here. Would it be different internally or its the same thing. In what cases does the return statement become useful in such statements.

Answer 1

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.

Answer 2

If you don't return from a non-void-return-type function, it'll lead to undefined behavior. Logically it should still function properly, but technically, on some compilers it'll work, on others it might not.

Compiling on gcc with -Wreturn-type enabled will also give you a warning (as you've mentioned):

warning: no return statement in function returning non-void [-Wreturn-type]

For example take this piece of code:

#include <iostream>

int foo() {
   int a = 5;
   int b = a + 1;
}

int main() { std::cout << "Test:"; std::cout << foo(); } // may print 6

From my compiler (gcc (MinGW.org GCC-6.3.0-1) 6.3.0), it does print Test:6, although there's no return. On other compilers though, it might do nothing, crashes, etc...

An example : ideone.com

So it's best if you use return properly.

Related : Why does flowing off the end of a non-void function without returning a value not produce a compiler error?