Thread: Recursion Revisited again, and again!

I have one more question. This is another interative loop in the chapter on searching that I had to convert to a recursive function.
Should I rewrite this function and break it into to two as I did with the sequential search?
I have the same problem of incrementing the position in the list.

Code:

//Function written for Test 5 Question 22
template<class elemType> 
int orderedArrayListType<elemType>::binarySearch(const elemType& item)
{
	static int first = 0;
	static int last = length - 1;
	static int mid = (first + last) / 2;

	if(first > last || mid == last || mid == first)
		return -1;
	if(list[mid] == item)
		   return mid;
	else if (list[mid] > item)
	{
		mid--;
		return binarySearch(item);
	}
    else
	{
		mid++;
		return binarySearch(item);
	}
}//end binarySearch

YEP!
It looks like I have to rewrite this one two for the same reason. Declaring static variables is ok for the first time through the function but the second time the number, that is in the list, is not found!
BUMMER!

The point is to avoid static vars unless you need them. Therefore, pass all the required variables that need to change with the function through arguments.
The code may be a little confusing here. I definitely recommend splitting it in two. Mid may be specifying the middle position of the array, but it's hardly a recommended name for a count variable, not to mention when you increment or decrement it, it won't be in the middle anymore, will it?
No, so make a public function that inits the count variable to the same value as mid has when the function begins. Then call an "internal", private search function with the value of the count. The internal search function will call itself with one less or one more to the count variable to do a loop.

Remember that static vars retain their value (only initialized once) for the function and won't die until the end of the program. The effect is pretty nasty one for the function as the second time you run it, mid won't be (first + last) / 2, but less or higher. So definitely recommend another function.

Hope you understand that.

Code:

template<class elemType> 
int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item)
{
	// We want to begin from the middle, so let's pass the value for the previous var mid.
	int mid = (first + last) / 2;
	return binarySearchImpl(item, mid);
}

//Function written for Test 5 Question 22
template<class elemType> 
int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int i)
{
	// Let's name our count variable i
	// Since we're never going to change last, let's make it const.
	const int last = length - 1;
	const int first = 0;
	//int mid = (first + last) / 2;

	// Our count variable is named i, much better name for a count variable.
	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

Now, I added comments. Do you think you can understand why I did what I just did?

binarySearchImpl has to take 3 parameters. The item being searched for, the low index, and the high index.

Code:

int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int first, int last)

You can't do it without doing that. This is because if it is less than the first middle value you pick then you only want to search in the first half.

You should also take a lesson from the C++ standard library and make the last parameter be the index of one-past the last item (equal to the count of items in other words). This saves a lot of places where you end up fudging it by adding or subtracting one. Those will actually ALL go away if you do that.

Originally Posted by iMalc

binarySearchImpl has to take 3 parameters. The item being searched for, the low index, and the high index.

Code:

int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int first, int last)

You can't do it without doing that. This is because if it is less than the first middle value you pick then you only want to search in the first half.

You should also take a lesson from the C++ standard library and make the last parameter be the index of one-past the last item (equal to the count of items in other words). This saves a lot of places where you end up fudging it by adding or subtracting one. Those will actually ALL go away if you do that.

Actually, since the function defines both first and last to constants of 0 and length - 1 repesctively, I don't think they need to be passed as arguments at all.
clegs: See my post above ^

Originally Posted by Elysia

Now, I added comments. Do you think you can understand why I did what I just did?

Hmm, I don't even know why you did what you just did (apart from the usage of const). It doesn't actually bring him any closer to a working solution.

Actually, since the function defines both first and last to constants of 0 and length - 1 repesctively, I don't think they need to be passed as arguments at all.

It's a bit hard to narrow the search space if you don't actually give the next iteration a different description of the search space.

clegs: You can do it without the extra 'count' parameter

Originally Posted by iMalc

Hmm, I don't even know why you did what you just did (apart from the usage of const). It doesn't actually bring him any closer to a working solution.

The recursion begins from mid, does it not? So I pass mid as the argument of i to the function.
This avoids making mid a static variable plus it also gives a counting variable a better name. Of course, I can rename i to something else as well.

Originally Posted by clegs

If I don't pass mid to binarySearchImpl() then doesn't it get reset each time the function calls itself?
DANG! I am revisiting recursion too many times, my head hurts!

In my code, I am passing the value of mid to the initial recursion. Then the function decrements or increments that value and passes it along to the next recursion.

You don't need to pass mid because each recursive call learns about the previous midpoint via the fact that either first or last will have been set to it. Other than that it doesn't care what the previous mid value was.

Sorry Cindy Legs I didn't mean to offend!

Originally Posted by iMalc

You don't need to pass mid because each recursive call learns about the previous midpoint via the fact that either first or last will have been set to it. Other than that it doesn't care what the previous mid value was.

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.

The way to do it is that first and last define the range of items you want to search in. Initially these are zero and length (rightmost value not included)
If first and last are the same then there are no values between them to look at, so the item was not found - return -1.
Then you pick the middle value and look at that.
Now if the value you are looking for is less than the value you looked at then you need to perform another search between first and mid.
If the value you are looking for was not less than the one you looked at, then you need to perform another search between mid and last.
Almost no subtractions or additions of 1 anywhere.