Recursion Revisited again, and again!

Show 80 post(s) from this thread on one page
Page 3 of 7 First 1234567 Last
• 12-05-2007
Elysia
Then it sounds like the original function is flawed, because what I proposed would seem to work fine for the loop posted, since it would increment i or decrement it and pass it along for the next recursion loop. It compares i (or mid, after it was incremeneted or decremented) to the value that's being searched for.
• 12-05-2007
iMalc
Quote:

Originally Posted by Elysia
But should it do that? First and last might as well be const, so it has to use a variable to count with, starting from mid and going down or up. This was originally just a loop, after all, so this makes the most sense too and it's the simplest IMO.

First and last will be const and their value will be whatever was passed from the previous recursive call.
No additional 'count' is required. It is most definitely not the simplest include it.

You could say that what makes sense is simply relative to your current line of thinking. Your current line of thinking is therefore not optimal.;) :confused: :)
• 12-05-2007
clegs
This is what I have and it isn't finding the numebr in the list - when it is there!
Code:

```template<class elemType> int orderedArrayListType<elemType>::binarySearch(const elemType& item) {         int first = 0;         int last = length - 1;         int mid = last - first / 2;         return binarySearchImpl(item, mid); } //Function written for Test 5 Question 22 template<class elemType> int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int i) {         const int last = length - 1;         const int first = 0;         if(first > last || i == last || i == first)                 return -1;         if(list[i] == item)                   return i;         else if (list[i] > item)         {                 return binarySearchImpl(item, i - 1);         }     else         {                 return binarySearchImpl(item, i + 1);         } }//end binarySearch```
I had to define first and last in binarySearch().
The numbers are in the list and with this code, they aren't found.
It does compile and it doesn't give a run time error, so those are two hash marks on the C++ side!
• 12-05-2007
clegs
So what you both are saying now has me totally confused!
• 12-05-2007
Elysia
Why don't you post the original algorithm? The original code you made into a recursive loop?
• 12-05-2007
clegs
This was the original nor-recursive function:
Code:

```template<class elemType> int orderedArrayListType<elemType>::binarySearch(const elemType& item) {         int first = 0;         int last = length -1;         int mid;         bool found = false;         while(first <= last && !found)         {                 mid = (first + last) / 2;                 if(list[mid] == item)                         found = true;                 else                         if(list[mid] > item)                                 last = mid - 1;                         else                                 first = mid + 1;         }         if(found)                 return mid;         else                 return -1; }```
• 12-05-2007
clegs
Wow! I decided to type that up before you asked then posted it and SPOOKY! You asked for it!
• 12-05-2007
matsp
That doesn't look at all right. You probably need two parameters to BinarySearchImpl, first and last. The algorithm goes a bit like this:
1. If (first >= last) can't find it.
2. mid = (last + first) / 2
3. If array[mid] == searchitem then return mid;
4. If array[mid] > searchitem then search again, with first = mid+1
5. Search again with last = mid-1;

I'll let you write the code to implement that.

--
Mats
• 12-05-2007
iMalc
Well I gotta go catch some ZZZ's any moment now.
You might find the searching article on my website helpful, as I spend most of the article focusing on binary search.
However I don't recall having recursive solutions on there since it is always better to use iteration for binary search.

Just remember that a tail-recursive call is the same as modifying the input parameters to the values you were passing to the recursive call. Or putting it the other way, for any values you change upon iteration, you could instead simply pass the new values to the next recursive call.

btw matsp, you might find my searching article interesting too.
• 12-05-2007
Elysia
It kinda looks like the original code is different from your recursive function. So, you can try to follow matsp's advice and re-write that recursion function.
• 12-05-2007
clegs
Ok! I will try it again.
I probably won't see my bed tonight!
Oh well, won't be the first time!
• 12-05-2007
clegs
Thanks everyone. I have to finish this tonight, so I won't be catching any ZZZ's.
I will keep plugging and post problems to anyone awake! Cause I shouldn't be!
• 12-05-2007
Elysia
It's still 10AM here, so I have plenty of time :D
• 12-05-2007
clegs
Cool!
It's 2am here!
I have to 'get up' at 5! HA, I won't have a problem with the alarm thi morning!
• 12-05-2007
clegs
Mats said two parameters passed to binarySearchImpl - first and last, but I actually need three right, item, first and last!
Show 80 post(s) from this thread on one page
Page 3 of 7 First 1234567 Last