recursive function

I want to create a recursive function that uses the binary search
algorithm. But every time I write the function into itself it doesn't
work. The system compiles the program but it freezes before anything
happens.If I take out the last line:<binsearch(val,array,high,low);>
it doesn't crash.
val is the value that we are searching for
array is the array that we are searching in
int binsearch(int val,int array[],int high,int low)
{
int mid;

mid=(low+high)/2;
if(val<array[mid])
{high=mid-1;}
else if(val>array[mid])
{low=mid-1;}
else
{return(val);}
binsearch(val,array,high,low);
}
I'm not sure if this is clear enough but just tell me any additional
info you need.
--
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

This is not seems to be c++ related..
any way - u r missing a 'return' statmement at the very end.

something like
return binsearch(val,array,high,low);

And if you would compile with any new c++ compiler he would warn about
it.
R.


On Jul 13, 10:35*am, hhc <cao...@yahoo.com> wrote:
> I want to create a recursive function that uses the binary search
> algorithm. But every time I write the function into itself it doesn't
> work. The system compiles the program but it freezes before anything
> happens.If I take out the last line:<binsearch(val,array,high,low);>
> it doesn't crash.
> val is the value that we are searching for
> array is the array that we are searching in
> int binsearch(int val,int array[],int high,int low)
> {
> * * int mid;
>
> * * mid=(low+high)/2;
> * * if(val<array[mid])
> * * {high=mid-1;}
> * * else if(val>array[mid])
> * * {low=mid-1;}
> * * else
> * * {return(val);}
> * * binsearch(val,array,high,low);}
>
> I'm not sure if this is clear enough but just tell me any additional
> info you need.
> --
> comp.lang.c.moderated - moderation address: c...@plethora.net -- you must
> have an appropriate newsgroups line in your header for your mail to be seen,
> or the newsgroup name in square brackets in the subject line. *Sorry.
--
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

First off, a good compiler should issue a warning that control
reaches end of non-void function. That means you should put
return binsearch(...) at the last line. Otherwise, if nothing
found, the function will return garbage.
Second, your calculation of mid always goes towards 0, which
effectively cuts off the high half of the array (its' never searched).
Use mid = low + (high - mid) / 2.
Third, what if the value you're looking for is not in the array?
You should return a special value (perhaps -1) to indicate this.
So the code would be:

int binsearch(int val,int array[],int high,int low)
{
int mid;

if (low > high) return -1;

mid = low + (low + high)/2;
if (val < array[mid])
{high = mid - 1;}
else if (val > array[mid])
{low = mid + 1;}
else
{return(val);}
return binsearch(val,array,high,low);
}
--
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

On Jul 13, 12:35*pm, hhc <cao...@yahoo.com> wrote:
> I want to create a recursive function that uses the binary search
> algorithm. But every time I write the function into itself it doesn't
> work. The system compiles the program but it freezes before anything
> happens.If I take out the last line:<binsearch(val,array,high,low);>
> it doesn't crash.
> val is the value that we are searching for
> array is the array that we are searching in
> int binsearch(int val,int array[],int high,int low)
> {
> * * int mid;
>
> * * mid=(low+high)/2;
> * * if(val<array[mid])
> * * {high=mid-1;}
> * * else if(val>array[mid])
> * * {low=mid-1;}
> * * else
> * * {return(val);}
> * * binsearch(val,array,high,low);}
>
> I'm not sure if this is clear enough but just tell me any additional
> info you need.
> --
> comp.lang.c.moderated - moderation address: c...@plethora.net -- you must
> have an appropriate newsgroups line in your header for your mail to be seen,
> or the newsgroup name in square brackets in the subject line. *Sorry.

i think you might be getting stuck in an infinite loop as the self
call to binsearch is not part of a conditional statement.
--
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

hhc wrote:
> I want to create a recursive function that uses the binary search
> algorithm. But every time I write the function into itself it doesn't
> work. The system compiles the program but it freezes before anything
> happens.If I take out the last line:<binsearch(val,array,high,low);>
> it doesn't crash.
> val is the value that we are searching for
> array is the array that we are searching in
> int binsearch(int val,int array[],int high,int low)
> {
> int mid;
>
> mid=(low+high)/2;
> if(val<array[mid])
> {high=mid-1;}
> else if(val>array[mid])
> {low=mid-1;}
> else
> {return(val);}
> binsearch(val,array,high,low);
> }
> I'm not sure if this is clear enough but just tell me any additional
> info you need.

This looks and sounds like homework, so my answer is intended to help
you find the answer for yourself.

If a recursive function 'freezes', it's probably failing to end the
recursion. Wait long enough and the freeze will probably stop, along with
a lot of (probably unhelpful) error messages.

Why not add something to help you understand what's going on ? If you
like using an interactive debugger, put a breakpoint on the entry
to that routine and see what's happening to its arguments.

Or if you don't like/have a debugger, put a call to printf at the beginning
of binsearch to tell you its arguments, or at least what 'high' and 'low' are.

Or walk through the code with these values:

Imagine that high=3 and low=1 on the first call to binsearch,
and that the value you seek is at array[3]. What value does mid
take ? What values are high and low set to before the first recursive
call to binsearch, if any ? And the next ? And the next ?

That way you may find enlightenment.
--
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

hhc wrote:
> I want to create a recursive function that uses the binary search
> algorithm. But every time I write the function into itself it doesn't
> work. The system compiles the program but it freezes before anything
> happens.If I take out the last line:<binsearch(val,array,high,low);>
> it doesn't crash.
> val is the value that we are searching for
> array is the array that we are searching in
> int binsearch(int val,int array[],int high,int low)
> {
> int mid;
>
> mid=(low+high)/2;
> if(val<array[mid])
> {high=mid-1;}
> else if(val>array[mid])
> {low=mid-1;}
> else
> {return(val);}
> binsearch(val,array,high,low);
> }
> I'm not sure if this is clear enough but just tell me any additional
> info you need.

I suppose it goes into an infinite loop and when the stack overflows, it
crashes. What error do you get when it crashes (segfault, ..?)
You should try using a debugger like gdb to see exactly when it crashes.
--
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

On Mon, 13 Jul 2009 02:35:19 -0500 (CDT), hhc <caohhc@yahoo.com>
wrote:

>I want to create a recursive function that uses the binary search
>algorithm. But every time I write the function into itself it doesn't
>work. The system compiles the program but it freezes before anything
>happens.If I take out the last line:<binsearch(val,array,high,low);>
>it doesn't crash.
>val is the value that we are searching for
>array is the array that we are searching in
>int binsearch(int val,int array[],int high,int low)
>{
> int mid;
>
> mid=(low+high)/2;
> if(val<array[mid])
> {high=mid-1;}

A consistent and visually obvious indenting style can save you a lot
of heartache when you write larger functions.

> else if(val>array[mid])
> {low=mid-1;}
> else
> {return(val);}

return is a statement, not a function. The parentheses are
unnecessary.

> binsearch(val,array,high,low);
>}
>I'm not sure if this is clear enough but just tell me any additional
>info you need.

Take a piece of paper and play computer. Let array = {1,2,3} and call
the function once with val = 2 and once with val = 1. Note what
happens when you call binsearch recursively in the second case. Where
does the second call return to?

I don't think you want to return val (since you know what it is in the
calling function). You probably want to return mid.

--
Remove del for email
--
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

On Tue, 14 Jul 2009 23:19:29 -0500 (CDT), shahav <shahav@gmail.com>
wrote:

>This is not seems to be c++ related..
>any way - u r missing a 'return' statmement at the very end.
>
>something like
> return binsearch(val,array,high,low);
>
>And if you would compile with any new c++ compiler he would warn about
>it.

Since this is a C group, your first comment is irrelevant and your
last inappropriate. But the middle one does address the problem.

--
Remove del for email
--
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

Hans-Bernhard Bröker wrote:
> hhc wrote:
>
>> The system compiles
>
> If so, either your compiler is totally broken, or the code you showed
> wasn't being compiled. I know that because there's a critical syntax
> error in it that no compiler is allowed let pass.

Which error is that? I couldn't find any such such error. I cut and
pasted the code into a file and compiled it with the command

gcc -std=c99 -pedantic -Wall -Wpointer-arith -Wcast-align \
-Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes -c binsearch.c

and gcc (4.1.2) agreed with me - it didn't generate any error messages,
just a few warning messages. The most serious was

warning: control reaches end of non-void function

That's not a syntax error, that's undefined behavior, but only if the
calling function tries to use the non-existent return value (6.9.1p12).
--
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

On Jul 15, 12:19*am, shahav <sha...@gmail.com> wrote:
> This is not seems to be c++ related..
> any way *- u r missing a 'return' statmement at the very end.
>

How is this not relevant to C++?

REH
--
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

Awhan Patnaik <awimagic@gmail.com> writes:
> i think you might be getting stuck in an infinite loop as the self
> call to binsearch is not part of a conditional statement.

Actually, it is. That part is correct. The parts that aren't have
already been explained by others.

DES
--
Dag-Erling Smørgrav - des@des.no
--
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.