i'm trying to learn recursion, so i decide to implement some algorithms that used recursion like binary search but i have some problems to understand why we need return on some cases like this one:

int binarysearch(int *arr, int x, int left, int right){
    if(right <= left){
        return -1;
    }
    int mid = (left   right) / 2;
    if(arr[mid] == x){
        return mid;
    }
    if(x < arr[mid])
        return binarysearch(arr, x, left, mid - 1);
    else 
        return binarysearch(arr, x, mid   1, right);
}

like we have no value that we need to return the only value we need are in the arguments, but when i remove the return statement i got some undefined behaviors.can someone explain to me why i got that undefined when i remove the return statement.

edit:

• this return statement: return binarysearch(arr, x, left, mid - 1);
• and this: return binarysearch(arr, x, mid 1, right);

CodePudding user response：

It is because the return value has to be propagated through the return value of every called function up into the original caller.

I will anotate every call by [i] just to distinguish different calls to the same function.

Lets say you have array { 1, 2 }, and you call printf("%d", binarysearch[1](array, 2, 0, 1));

Then

• mid = 0 (because of rounding down when dividing two integers)
• 2 < arr[0] ~ 2 < 1 = 0 (0 means false in C)

And therefore binarysearch[2](array, 2, 1, 1); is called inside binarysearch[1]. In this new function the mid = 1 and arr[1] == 2, so the function binarysearch[2] returns 1.

But binarysearch[2] was called inside binarysearch[1] so the value 1 is now inside binarysearch[1] and in order to get the value to the printf, we have to return it again.

If you delete the return (which I am surprised that the compiler even allows you to do), then the value returned from binarysearch[2] is discarded and binarysearch[1] ends without returning the value to the printf, but printf is expecting the value to be there, so it just takes whatever is in memory at that point and that results in undefined behavior.

I hope it is somewhat understandable.

CodePudding user response：

What I understand from your question is that why we need to return the statements which are already present in the function.

So firstly the concept of recursion is function calling itself continuously.

Next the concept of binary search is to find an element in a list by dividing it into two.

It finds out the middle and compares it with the search element and if it is greater then the search value it carries out the search in the same way in the other part of the search.

The return statements you have mentioned are to call the functions again to repeat the function of search. i.e, to carry out the search in either first part of the list or second.

It does this function repeatedly until the element to be searched is found.

In simple words, the return statement takes back the control back to the start of the function. You can't have neglected the return because the function is declared as int and it has to have a return statement