0

While learning recursion I tried to implement binary search.Both my functions provide the correct answer.Can someone explain why?

I feel that in the first function the recursive function return the values found to the previous functions but in the second function the recursive functions are just called and the call which hits the base case or which gets the answer returns directly to main().

Can someone please confirm if in the second case the function where the base case is reached or the element is found it's returned directly to main() and not to the previous recursive functions in the callstack, if there is one needed in the second case.

int bins1(int *arr,int l,int h,int el){
    if(l>h){
        return -1;
    }
    int mid = (l+h)/2;
    if(arr[mid] == el){
        return mid+1;
    }
    else if(arr[mid] > el){
        return bins1(arr,mid+1,h,el);
    }
    else if(arr[mid] < el){
        return bins1(arr,l,mid-1,el);
    }
}



int bins2(int *arr,int l,int h,int el){
    if(l>h){
        return -1;
    }
    int mid = (l+h)/2;
    if(arr[mid] == el){
        return mid+1;
    }
    else if(arr[mid] > el){
        bins2(arr,mid+1,h,el);
    }
    else if(arr[mid] < el){
        bins2(arr,l,mid-1,el);
    }
}
Krishna Prasad
  • 21
  • 4
  • Do read [Understanding how recursive functions work](https://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work) – Achal Jul 29 '19 at 19:31
  • 1
    Possible duplicate of [C and C++ functions without a return statement](https://stackoverflow.com/questions/32513793/c-and-c-functions-without-a-return-statement) – Justin Jul 29 '19 at 19:32
  • 4
    You have undefined behavior, because control flow reaches the end of `bins2` without reaching a `return` statement. Notice the compiler warnings: https://godbolt.org/z/Ro_7ob "warning: control reaches end of non-void function" – Justin Jul 29 '19 at 19:32
  • It looks like the question is more about undefined behavior in `bins2`of not returning a value from a function than recursion. `bins2` does not work even though it appears to give you the correct answer on the values tested under your envioronemnt. It makes use of undefined behavior. – drescherjm Jul 29 '19 at 19:34
  • Again the second code is broken so there is no confirming what happens in the broken code. – drescherjm Jul 29 '19 at 19:41
  • bins2 works for all cases – Krishna Prasad Jul 29 '19 at 19:42
  • 1
    ***bins2 works for all cases*** That you have tried with your compiler and optimization settings. It's still broken. It violates a rule of the language. All return paths of a non void function must return a value. `bins2` violates this. – drescherjm Jul 29 '19 at 19:42
  • 1
    "Can someone please confirm if in the second case the function where the base case is reached or the element is found it's returned directly to main() and not to the previous recursive functions in the callstack." It's undefined behavior. Anything can happen. As you can see from that godbolt.org link, with no optimizations, it returns to the previous point in the callstack, and various optimizations give different results, such as `-O3` which results in arbitrary code being executed (whatever happens to be after `bins2`'s code) – Justin Jul 29 '19 at 19:43
  • 1
    @KrishnaPrasad that method of calling a function but not returning the result and hoping for the best may work for you on your machine with your compiler, but it by no means "works for all cases": [ideone](https://ideone.com/SIx2Qn) – scohe001 Jul 29 '19 at 19:46

0 Answers0