0

In the below binary search function returning value of integer type, why should we use the return value in both the else if statement when there is a recursive call? The code won't work if I directly use recursive call rather than using it in return.

int binarysearch(int l,int h,int key)
{
  int mid;
  mid=(l+h)/2;
  if(l<=h)                             
  {
    if(key==a[mid])
      return mid;
    else if(key>a[mid])
      return(binarysearch(mid+1,h,key));
    else if(key<a[mid])
      return(binarysearch(l,mid-1,key));
  }
  else
    return -1;
}
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Ayush Kumar
  • 13
  • 3
  • 1
    Related: this function needs to be rewritten so that there is only one single recursive call. It should end with something like `return binarysearch(low, high, key);`. Otherwise you have only produced a horribly slow bloat function that's so much worse than just writing a single loop - since the compiler can't tail call optimize it. Which in turn makes it obvious that there is absolutely no need to use recursion in this case. Start by asking yourself "why am I using recursion here"? See if you can manage to come up with another answer than "because I'm learning recursion". – Lundin Jan 08 '20 at 15:00
  • If I use low=mid+1. Then if I put it inside function as you said binarysearch(low,high,key) .what's the difference – Ayush Kumar Jan 08 '20 at 15:04
  • The difference is that if you have several "branches" (if else scenarios) with recursive calls, the parameter calculations will happen in those branches and you can't be certain that the compiler can optimize away the recursive calls. (I tried gcc & clang for x86 and it turns out they _can_ optimize this particular code, but I wouldn't count on it.) – Lundin Jan 08 '20 at 15:14
  • @Lundin That function cannot be _horribly slow_. Its runtime complexity is still O(log n), which is fast enough for all practical purposes. – Lxer Lx Jan 08 '20 at 15:16
  • Ok I got it probably,I should use one return statement in the end of the code and modify the value of of low and high in the else if statement so that I have a single recursive call.Well thanks for the information. – Ayush Kumar Jan 08 '20 at 15:19
  • @AyushKumar You can, but you don't have to. It is a stylistic issue. The function is fine. – Lxer Lx Jan 08 '20 at 15:23
  • @LxerLx The problem is that computer programs run on computers. A function call on a computer is a very expensive operation, unlike a simple comparison. It doesn't matter much if the search algorithm is O(log n) or O(42) because the function call overhead is vast in comparison to the actual algorithm. In addition, repeated function calls would lead to a huge stack peak usage. So for this code to be close to resembling effective, we must guarantee that there are no repetitive function calls. Compilers can only be trusted to do that if there is a clear call for tail-cail optimization. – Lundin Jan 08 '20 at 15:24
  • The concept of real-world computers is typically completely alien to computer scientists though. These have function call overhead, branch prediction, data cache, register inlining, ISA quirks etc etc. We can't run algorithms on theoretical magic machines yet. And until we do, I suspect that C will keep outperforming all pretty high level languages... – Lundin Jan 08 '20 at 15:27
  • @Lundin As Knuth wisely said, "The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; **premature optimization is the root of all evil (or at least most of it) in programming**." – Lxer Lx Jan 08 '20 at 15:30
  • @LxerLx Except this _isn't_ pre-mature optimization, it's real-world optimization. We are talking about adding O(log n) extra function calls. Lets say you have n=1000, you'll end up with something like 10 extra function calls that just sits there like useless bloat. Also, binary search is branch-intensive and if the compiler can't deduct the execution path because of the function calls, this will cause further performance losses. If unlucky, we may end up in a scenario where simply iterating through all 1000 elements with brute force `for` might vastly outperform the binary search algorithm. – Lundin Jan 08 '20 at 15:38
  • 1
    @Lundin We are discussing in a vacuum, in the absence of measured performance issues and without knowing the bottlenecks of a whole concrete program. In the first place, I wouldn't write that function recursively. But, I wouldn't bother myself about optimizing a function with O(log n) worst-case complexity either, unless it is a bottleneck. Premature means, to me, "too early in the life cycle". – Lxer Lx Jan 08 '20 at 17:50
  • @LxerLx Try to code heavily memory restricted embedded systems then. It's not so much a performance issue there, as a stack overflow hazard. Failure to tail-call optimize will cause the program to crash in subtle and horrible ways. – Lundin Jan 09 '20 at 15:15

3 Answers3

5

While its return value is of type int, the function must return a value. Every place where it returns must return a value. When the recursive call made by the current function invocation returns, it gives you the answer; you must return that answer to the calling context — either the next level up the recursion chain or the original caller.

If you don't return a value, you invoke undefined behaviour, which is A Bad Thing!™

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • If you wanted, you could maintain the answer in an external variable and use a pointer to it and have a void return type for the function. In my company, our coding standard doesn't allow having that type of construct in a return, because it's hard to test. – rallen911 Jan 08 '20 at 14:56
  • @rallen911 — and become thread-unsafe and harder to use. But you also modify the function to return `void` (nothing), and if it returns nothing, then obviously you don't return a value in the `return` statements. – Jonathan Leffler Jan 08 '20 at 14:58
  • @rallen911 well recursive functions are probably much harder to test than just calling a function in a `return` – Guillaume Petitjean Jan 08 '20 at 15:01
  • Not returning a value (by reaching the closing brace) from a function declared to return a value does not cause undefined behavior. A caller using the return value of a function that did not return a value causes the behavior to not be defined by the C standard. – Eric Postpischil Jan 08 '20 at 21:10
  • @EricPostpischil — yes, but I was trying to keep my answer comprehensible to a tyro. The difference is usually negligible, but not always. In particular, the difference would not apply meaningfully to the recursive search code. – Jonathan Leffler Jan 08 '20 at 21:13
  • The truth can be stated for beginners, such as “When a function returns a value to be used, it must…” – Eric Postpischil Jan 08 '20 at 21:18
  • C11 [§6.8.6.4 The `return` statement](http://port70.net/~nsz/c/c11/n1570.html#6.8.6.4p1) specifies the constraint: _A `return` statement with an expression shall not appear in a function whose return type is `void`. A `return` statement without an expression shall only appear in a function whose return type is `void`._ That only leaves 'falling off the end of a function' as a way not to return a value from a non-`void` function. – Jonathan Leffler Jan 08 '20 at 23:21
  • @JonathanLeffler: I did not say to teach nuance. Teaching nuance would include teaching that a function declared to return a value does not always have to return a value, if the caller does not use it. My example elides that nuance yet is truthful. I am opposed to teaching falsehoods. They are objectively bad and implant knowledge that must be unlearned. – Eric Postpischil Jan 09 '20 at 00:37
1

If the prototype of your function defines that its return type is a non-void data, then in the body of that function a value of the type specified in the prototype MUST be returned. Note that in the prototype of your function is explicit that a value of type "int" must be returned:

int binarysearch(int l, int h, int key);

In the body of its function there are some conditions. The conditions lead to distinct execution instructions. You need to verify that, at the end of each statement, the value of the same type return of the function will, in fact, be returned.

If you do not want to use return, your function should have the following prototype:

void binarysearch(int l, int h, int key, int *mid);

In this case, you would use pointer to retrieve the value of "mid" out of the inner context of this function.

cayo
  • 17
  • 4
  • The first sentence is not true. The C standard permits a function declared to return a value not to return a value (by reaching its closing brace) provided the caller does not attempt to use the return value. – Eric Postpischil Jan 08 '20 at 21:13
  • Breaking a void function using the "return" clause is a bad programming practice. Any void function can be perfectly performed without breaking it with "return;". My solution explains how to program using best practices! Making it work doesn't mean it's correct! – cayo Jan 08 '20 at 21:30
  • My comment is not about a “void function,” by which I presume you mean a function with return type `void`. It is about a function that is declared to return a type other than `void`. The first sentence of this answer is false: The C standard does not require a function with non-`void` return type to return a value, and doing so does not, in itself, render the behavior not defined by the standard. – Eric Postpischil Jan 09 '20 at 00:35
0

It is not clear what you are asking. I think you want a single return statement, which could be done with this edit of your function:

extern int a[];
int binarysearch(int l,int h,int key)
{
  int mid;
  mid=(l+h)/2;
  if(l<=h) {
    if(key>a[mid]) {
      mid = binarysearch(mid+1,h,key);
    } else if(key<a[mid]) {
      mid = binarysearch(l,mid-1,key);
    }
  } else {
    mid = -1;
  }
  return mid;
}

Your original function caused a compiler diagnostic for me:

bb.c:17:1: warning: control may reach end of non-void function [-Wreturn-type] }

Which appears to be a spurious compiler warning, as it sees that the construct:

if (a == b) {
    return ...;
} else if (a < b) {
    return ...;
} else if (a > b) {
    return ...;
}

has some other possibility. I added:

return -42;

and that seemed to satisfy it.

mevets
  • 10,070
  • 1
  • 21
  • 33