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  
 
 [ 6 post ] 

 Relevant Pages 

1. Need Help with Recursive Depth first search w/backtracking

2. Help needed in recursive equations

3. recursive function help needed

4. Recursive algorithm - help needed

5. Recursive function help needed :-)

6. Need Help on Recursive Function.

7. Help needed for Recursive Class Design

8. Help needed with non-recursive floodfill

9. Help Needed for Recursive Class Design

10. Compile Error=> Need help from expert

11. Needed help from Expert to slove my error

12. Inexplicable System call failure - HELP - expert needed

 

 
Powered by phpBB® Forum Software