binary search (Recursive implementation)

Question

I tied to write binary search code in Recursive. and I first wite this:

int rSearch(int numbers[],int start, int end, int x){
    int mid;
    if(start <= end){
        mid = (start + end)/2;
        if(numbers[mid] == x)
            return mid;
        else if(numbers[mid] > x)
            rSearch2(numbers, start, mid-1, x);
        else
            rSearch2(numbers, mid+1, end, x);

    } else
        return -1;
}

and it's work perfect. but after i searched about it I understand I have to write code like this:

int rSearch2(int numbers[],int start, int end, int x){
    int mid;
    if(start <= end){
        mid = (start + end)/2;
        if(numbers[mid] == x)
            return mid;
        else if(numbers[mid] > x)
            return rSearch2(numbers, start, mid-1, x);
        else
            return rSearch2(numbers, mid+1, end, x);

    } else
        return -1;
}

because in first code we may not have return value.
my question is why first code worked?

@melpomene Silly question, but is this actually undefined behavior in C? Or is it just unspecified? I'm pretty sure it's undefined, but I'm having trouble finding a reference on that. — templatetypedef, Dec 08 '18 at 18:00
@templatetypedef "*If the `}` that terminates a function is reached, and the value of the function call is used by the caller, the behavior is undefined.*" [6.9.1p12](http://port70.net/~nsz/c/c11/n1570.html#6.9.1p12) — melpomene, Dec 08 '18 at 18:02

score 1 · Answer 1 · answered Dec 08 '18 at 18:03

Welcome to the wonderful world of Undefined Behavior. In C, if you forget to return a value from a function and try using that value, you get what's called undefined behavior, meaning that there are no requirements whatsoever on what can then happen. It's entirely possible that by pure coincidence the code will work on your system, but compiling that same code on another system might end up having the same code fail to produce the right value. Although I can't envision this ever happening, technically speaking undefined behavior could cause your program to reformat the user's hard drive while playing the lyrics to "Gangnam Style."

The reason that this probably worked on your system is that on many architectures small return values are stored in a specialized register, and the way that a return statement is compiled is by loading a value into that register and then jumping out of the function. Therefore, if you eventually return a value in a recursive chain and then forget to return values elsewhere, that original value might coincidentally still be in the register as though you'd properly returned it. But you can't rely on this, as mentioned above - it's not portable.

Stefan Becker · Answer 2 · 2018-12-08T19:13:33.360

To expand on @templatetypedef (sorry, this would be unreadable as a comment): using Linux gcc x86_64 as an example:

$ gcc -S dummy.c -fverbose-asm -o -
...
# dummy.c:6:             return mid;
    movl    -4(%rbp), %eax  # mid, _12
    jmp .L1 #
...
# dummy.c:8:             rSearch2(numbers, start, mid-1, x);
...
    call    rSearch2    #
    jmp .L7 #
.L5:
# dummy.c:10:             rSearch2(numbers, mid+1, end, x);
...
    call    rSearch2    #
    jmp .L7 #
.L2:
# dummy.c:13:         return -1;
    movl    $-1, %eax   #, _12
    jmp .L1 #
.L7:
.L1:
# dummy.c:14: }
    leave
    .cfi_def_cfa 7, 8
    ret

On this platform the return value is stored in the register %eax. From the assembler code it is obvious that

eax is either initialized or
not touched when returning from a recursive call to rSearch2()

This is a classic case of why compiler warnings are the programmers (best?) friend:

$ gcc -Wall -Werror -S dummy.c -fverbose-asm -o dummy.s
dummy.c: In function ‘rSearch2’:
dummy.c:14:1: error: control reaches end of non-void function [-Werror=return-type]
 }
 ^
cc1: all warnings being treated as errors

binary search (Recursive implementation)

2 Answers2