Passing return values over recursive functions in C

Question

I was writing a binary search function:

int binsearch(int seq[], int start, int end, int key)
{
    int len = end - start + 1;
    int mid = (start + end) / 2;

    if (len <= 0)
        return -1;
    else if (key == seq[mid])
        return mid;
    else if (key < seq[mid])
        binsearch(seq, start, mid - 1, key);
    else
        binsearch(seq, mid + 1, end, key);
}

I was not aware that I returned only once in the innermost call. I compiled it with gcc in my laptop, and it worked perfectly.

However, when I compiled that code in a cloud computer using clang, it threw me a warning that the control could reach the end of a non-void function. Then, I put another variable there to pass the return value over recursive calls.

Why did gcc compile it without any warning and yet the function gave the correct output? Is this a kind of compiler optimization? I thought C would not pass the return value automatically over recursive calls.

Not returning a value in a function declared to return a value leads to undefined behavior. Anything could happen, including seemingly working. — Some programmer dude
– Some programmer dude, Commented Nov 10, 2016 at 14:00
Looks like all you need to do is add a return keyword before the calls to binsearch in the final else if and else. — wablab
– wablab, Commented Nov 10, 2016 at 14:01
Side note: once you fix your code by adding a return preceding each call to binsearch, you can get rid of all the elses. — barak manos
– barak manos, Commented Nov 10, 2016 at 14:04
@barakmanos: You are correct, but beware of the discussions about multiple return point in a function. Some people take coding standards like MISRA as a religion ... — too honest for this site
– too honest for this site, Commented Nov 10, 2016 at 14:07

Vlad from Moscow · Accepted Answer · 2016-11-10 14:02:10Z

2

The compiler says that these paths of the function

else if (key < seq[mid])
    binsearch(seq, start, mid - 1, key);
else
    binsearch(seq, mid + 1, end, key);

do not have return statements.

You need at least to write

else if (key < seq[mid])
    return binsearch(seq, start, mid - 1, key);
else
    return binsearch(seq, mid + 1, end, key);

answered Nov 10, 2016 at 14:02

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Bathsheba · Accepted Answer · 2016-11-10 14:02:19Z

1

The behaviour of your program is undefined; you must explicitly return a value on all control paths.

A kind compiler will warn you of this; gcc certainly does if you set an appropriate warning level.

I believe that the fix in your case is to write return before your binsearch calls.

(The only exception to this is int main(...) where the compiler must introduce an implicit return 0; if it's missing).

answered Nov 10, 2016 at 14:02

Bathsheba

235k35 gold badges376 silver badges504 bronze badges

1 Comment

W. Zhu Over a year ago

I understand now. I compiled with gcc again by including -Wall and indeed it gave me the warning. Thank you.

Collectives™ on Stack Overflow

Passing return values over recursive functions in C

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related