# Thread: Recursion Revisited again, and again!

1. 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.

2. 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.

3. 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!

4. So what you both are saying now has me totally confused!

5. Why don't you post the original algorithm? The original code you made into a recursive loop?

6. 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;
}```

7. Wow! I decided to type that up before you asked then posted it and SPOOKY! You asked for it!

8. 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

9. 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.

10. 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.

11. Ok! I will try it again.
I probably won't see my bed tonight!
Oh well, won't be the first time!

12. 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!

13. It's still 10AM here, so I have plenty of time

14. Cool!
It's 2am here!
I have to 'get up' at 5! HA, I won't have a problem with the alarm thi morning!

15. Mats said two parameters passed to binarySearchImpl - first and last, but I actually need three right, item, first and last!