Recursive experts -- I need help!
Author Message
Recursive experts -- I need help!

Dear experts,

I have another recursion problem. I have to take a non recusive function
given to me and rewrite it so that it is recursive as part of my
assignment.  Personally, I hate recursion.  I feel if the program isn't
broken, don't fix it.  But, if I want to pass this class i must complete
the damn assignment.

Here is the function, which is a binary search function, to be changed to
recursive.....

int b_search(int a[], int x, int n)
{
int lo, mid, hi; /*mid=midpoint of lo and high */
int posn=-1;  /* initialize position of item to -1, not found */
int found=0;  /* found flag, initialized to false */

lo=0; hi=n-1; /* boundaries of the array */
while (lo<=hi&&!found)
{
mid=(lo+hi)/2;
if(a[mid]==x)
{
found=1;
posn=mid;
}
else if (a[mid]<x)
lo=mid+1;
else
hi=mid-1;
}
return(posn);

Quote:
}

/****************************************************/
Here is what I have written.  I tested it and the function never gets
called.  Again, my base case is probably my error.  The function header
must be changed to the following "int b_search(int a[], int x, int lo, int
hi)".
Here goes......

int b_search(int a[], int x, int lo, int hi)
{
int posn, mid;

mid=(lo+hi)/2;  /* I calculate the midpoint. */

if (a[mid]==x)  /* Base case, when the search has found
posn=mid;        what it is looking for stop. */

else if (a[mid]<x){           /* if "a[mid]" is smaller that "x"
lo=mid+1;                        increment "mid", and call the
b_search(a, x, lo, hi);}      function again. */
else{
hi=mid-1;                     /* if "a[mid]" is greater that "x"
b_search(a, x, lo, hi);        decrement "mid", and call the
}                                      function again. */

return(posn);

Quote:
}

In my view this damn thing should work, but of course I have not graduated
yet.  Can you help me.  My prof explained that only minor changes needed to
be made?
--
Trevor Robb

Fri, 29 Sep 2000 03:00:00 GMT
Recursive experts -- I need help!

: Here is what I have written.  I tested it and the function never gets
: called.  Again, my base case is probably my error.  The function header
: must be changed to the following "int b_search(int a[], int x, int lo, int
: hi)".
: Here goes......
: In my view this damn thing should work, but of course I have not graduated
: yet.  Can you help me.  My prof explained that only minor changes needed to
: be made?

Your problem is simple: Your comments are just extending over line ends, so
the code that is actually compiled is

: int b_search(int a[], int x, int lo, int hi)
: {
:    int posn, mid;

:    mid=(lo+hi)/2;  /* I calculate the midpoint. */
:
:    if (a[mid]==x)
:    else if (a[mid]<x){
:    else{
:       hi=mid-1;

:    return(posn);
: }
I am wondering that it compiles at all -- too much open braces. Anyway, you
do not even have to change the prototype. Look at this:

int b_search(int a[], int x, int hi)
{
int posn, mid;

mid=(lo+hi)/2;  /* I calculate the midpoint. */

if (a[mid]==x)
posn=mid;
else if (a[mid]<x){
lo=mid+1;
b_search(a, x + lo, hi - lo);
} else {
hi=mid-1;
b_search(a, x + lo,hi - lo);
}
return(posn);

Quote:
}

--
\|/

------------------------------------------------oOO-(_)-OOo---------

Web-Page: http://www.pci.uni-heidelberg.de/tc/usr/joerg
--------------------------------------------------ooO-Ooo-----------

Fri, 29 Sep 2000 03:00:00 GMT
Recursive experts -- I need help!

The biggest problem here is your comments.  They are spanning over your
code.  Do you have a de{*filter*}?  If not, they you can simply use pencil and
paper.  Make a sorted array of 5 things and search for an item that is in
the array and an item that is not using your algorithm.
--
Hypertext C-FAQ: http://www.*-*-*.com/ ~scs/C-faq/top.html
C-FAQ ftp: ftp://rtfm.mit.edu, C-FAQ Book: ISBN 0-201-84519-9
Try "C Programming: A Modern Approach" ISBN 0-393-96945-2
Want Software?  Algorithms?  Pubs? http://www.*-*-*.com/

Quote:

>Dear experts,

>I have another recursion problem. I have to take a non recusive function
>given to me and rewrite it so that it is recursive as part of my
>assignment.  Personally, I hate recursion.  I feel if the program isn't
>broken, don't fix it.  But, if I want to pass this class i must complete
>the damn assignment.

>Here is the function, which is a binary search function, to be changed to
>recursive.....

>int b_search(int a[], int x, int n)
>{
>   int lo, mid, hi; /*mid=midpoint of lo and high */
>   int posn=-1;  /* initialize position of item to -1, not found */
>   int found=0;  /* found flag, initialized to false */

>   lo=0; hi=n-1; /* boundaries of the array */
>   while (lo<=hi&&!found)
>    {
>      mid=(lo+hi)/2;
>      if(a[mid]==x)
>      {
>        found=1;
>        posn=mid;
>      }
>      else if (a[mid]<x)
>        lo=mid+1;
>      else
>        hi=mid-1;
>     }
>     return(posn);
>}
>/****************************************************/
>Here is what I have written.  I tested it and the function never gets
>called.  Again, my base case is probably my error.  The function header
>must be changed to the following "int b_search(int a[], int x, int lo, int
>hi)".
>Here goes......

>int b_search(int a[], int x, int lo, int hi)
>{
>   int posn, mid;

>   mid=(lo+hi)/2;  /* I calculate the midpoint. */

>   if (a[mid]==x)  /* Base case, when the search has found
>      posn=mid;        what it is looking for stop. */

>   else if (a[mid]<x){           /* if "a[mid]" is smaller that "x"
>      lo=mid+1;                        increment "mid", and call the
>      b_search(a, x, lo, hi);}      function again. */
>   else{
>      hi=mid-1;                     /* if "a[mid]" is greater that "x"
>      b_search(a, x, lo, hi);        decrement "mid", and call the
>      }                                      function again. */

>   return(posn);
>}
>In my view this damn thing should work, but of course I have not graduated
>yet.  Can you help me.  My prof explained that only minor changes needed to
>be made?
>--
>Trevor Robb

Fri, 29 Sep 2000 03:00:00 GMT
Recursive experts -- I need help!

I am sorry that I have been a bit fast and lazy in answering the question
yesterday, here is the corrected code:

int b_search(int a[], int x, int hi)
{
int posn, mid;

mid = hi / 2;  /* I calculate the midpoint. */

if (a[mid]==x)
posn=mid;
else if (a[mid]<x){
mid++;
posn = mid + b_search(a + mid, x, hi - mid);
} else {
mid--;
posn = b_search(a, x, mid);
}
return(posn);

Quote:
}

Of course, "posn" has to be set in all branches of the if statements and some
other things were also bad.
One final remark: Usually, one drops the test for equality "a[mid]==x",
since this occurs very seldom and writes the routine like the following:

int b_search(int a[], int x, int hi)
{
int posn, mid;

if(hi <= 1) return(0);
mid = hi /2;  /* I calculate the midpoint. */

if (a[mid]<x){
mid++;
posn = mid + b_search(a + mid, x, hi - mid);
} else {
posn = b_search(a, x,mid);
}
return(posn);

Quote:
}

The first comparison ensures that the code terminates (was missing in original
as well).

Note the "hi=mid" in the second case, since we haven't tested "a[mid]" for
equality. This code seems to be less optimal, but you win in most cases,
where "a[mid] != x", since you only need *one* comparison instead of two
(usually, comparisons of "x" are more expensive than the first comparison
"hi <= 1").

--
\|/

------------------------------------------------oOO-(_)-OOo---------

Web-Page: http://www.pci.uni-heidelberg.de/tc/usr/joerg
--------------------------------------------------ooO-Ooo-----------

Sat, 30 Sep 2000 03:00:00 GMT
Recursive experts -- I need help!

Quote:
>Dear experts,

>/****************************************************/
>Here is what I have written.  I tested it and the function never gets
>called.  Again, my base case is probably my error.  The function header
>must be changed to the following "int b_search(int a[], int x, int lo, int
>hi)".
>Here goes......

>int b_search(int a[], int x, int lo, int hi)
>{
>   int posn, mid;

>   mid=(lo+hi)/2;  /* I calculate the midpoint. */

>   if (a[mid]==x)  /* Base case, when the search has found
>      posn=mid;        what it is looking for stop. */

>   else if (a[mid]<x){           /* if "a[mid]" is smaller that "x"
>      lo=mid+1;                        increment "mid", and call the
>      b_search(a, x, lo, hi);}      function again. */
>   else{
>      hi=mid-1;                     /* if "a[mid]" is greater that "x"
>      b_search(a, x, lo, hi);        decrement "mid", and call the
>      }                                      function again. */

>   return(posn);
>}
>In my view this damn thing should work, but of course I have not graduated
>yet.  Can you help me.  My prof explained that only minor changes needed to
>be made?
>--
>Trevor Robb

Umm.... you might take a look at your comments; they comment out most
of your code.  The rest of it is your homework and your job to do; or
what is the POINT of graduating???

Sat, 30 Sep 2000 03:00:00 GMT
Recursive experts -- I need help!

Look at the declaration of function 'bsearch' in your program then look
at how you've _actually_ used it in your program when you're making the
recursive calls.

Mon, 02 Oct 2000 03:00:00 GMT

 Page 1 of 1 [ 6 post ]

Relevant Pages

Powered by phpBB® Forum Software