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.

Recursive functions work exactly like non-recursive functions. — molbdnilo, Jun 10 '21 at 07:43
for me it always helps to introduce a dummy function, call it `binarySearch2`, implement it the same as `binarySearch`, and replace `return binarySearch(a, size, x, mid+1, high);` with `return binarySearch2(a, size, x, mid+1, high);`. Now you can reason about `binarySearch` as if there was no recursion — 463035818_is_not_an_ai, Jun 10 '21 at 07:45
In particular, every function call returns to the place where it was called. There is no mechanism that makes recursive functions somehow return to the "initial caller". — molbdnilo, Jun 10 '21 at 08:11
Another way of thinking about it is to use `int result = binarySearch(a, size, x, mid+1, high);` and then have `return result ;`. In other words, you make a call to a function (storing the result) and then you return that result. The fact that the function you call happens to be the one you're already in doesn't really matter. — TripeHound, Jun 10 '21 at 08:20

silverfox · Answer 1 · 2021-06-10T08:00:19.867

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?

Thanks for the explanation but actually i am confused in the return particularly in my given example of binary search where recursion is taking place. — Karmveer Singh, Jun 10 '21 at 08:04
@KarmveerSingh Well, it's not much of a difference as you don't use that value anywhere else, but as I state above, on *some* compilers/platforms it might give off weird results, so if you do use your code above without the `return`, be prepared. — silverfox, Jun 10 '21 at 08:06

score 0 · Accepted Answer · answered Jun 12 '21 at 13:21

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.

How does the return statement work in recursion?

2 Answers2