0

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?

Improve this question
3
  • 2
    Undefined behavior is undefined. Commented Dec 8, 2018 at 17:59
  • @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. Commented Dec 8, 2018 at 18:00
  • 2
    @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 Commented Dec 8, 2018 at 18:02

2 Answers 2

Reset to default
1

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.

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

Comments

1

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
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.