Recursion Revisited again, and again!

This is a discussion on Recursion Revisited again, and again! within the C++ Programming forums, part of the General Programming Boards category; I have one more question. This is another interative loop in the chapter on searching that I had to convert ...

  1. #16
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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!
    Last edited by clegs; 12-05-2007 at 01:06 AM.

  2. #17
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,614
    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.
    Last edited by Elysia; 12-05-2007 at 01:17 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #18
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Ok, I kinda get what you are saying, but I AM confused, big surprise, huh!

    I want first to always be '0' and last to always be 'length - 1'. So I don't have to pass them in the argument list, I just need to pass mid, but rename (these names were used in the original iterative function - which worked just fine, I might add) it in the binarySearchImpl() function?

    Let me post what I have so far:
    Code:
    template<class elemType> 
    int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item)
    {
    	return binarySearchImpl(item, 0);
    }
    
    //Function written for Test 5 Question 22
    template<class elemType> 
    int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int first)
    {
    	int last = length - 1;
    	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 binarySearchImpl(item, );
    	}
        else
    	{
    		mid++;
    		return binarySearchImpl(item);
    	}
    }//end binarySearch
    I have binarySearchImpl() as a private function and binarySearch as public in my class definition.
    Where do I go from here and why?
    Thank you!

  4. #19
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,614
    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?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #20
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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.
    Last edited by iMalc; 12-05-2007 at 01:30 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #21
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Actually this is what I have now. I am getting an error that I don't have a default value for parameters 3 and 4 in my binarySearchImpl function declaration in the class definition.
    declaration statment:
    Code:
    private:
    	int binarySearchImpl(const elemType& item, int first = 0, int last, int count);
    And there are the two function definitions:
    Code:
    template<class elemType> 
    int orderedArrayListType<elemType>::binarySearch(const elemType& item)
    {
    	first = 0;
    	last = length - 1;
    	mid = last - first / 2;
    
    	return binarySearchImpl(item, first, last, mid);
    }
    
    //Function written for Test 5 Question 22
    template<class elemType> 
    int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int first, int last, int count)
    {
    	if(first > last || count == last || count == first)
    		return -1;
    	if(list[count] == item)
    		   return count;
    	else if (list[count] > item)
    	{
    		count--;
    		return binarySearchImpl(item, first, last, count);
    	}
        else
    	{
    		count++;
    		return binarySearchImpl(item, first, last, count);
    	}
    }//end binarySearch

  7. #22
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,614
    Quote Originally Posted by iMalc View Post
    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 ^
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #23
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by Elysia View Post
    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
    Last edited by iMalc; 12-05-2007 at 01:36 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #24
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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!

  10. #25
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    iMalc - I am a her! - Cindy, my name is Cindy.
    Not that it is a big deal right now!
    At this time of night I could be a him!
    I have to get up in 4 hours to go to work! Can you say tired?

  11. #26
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,614
    Quote Originally Posted by iMalc View Post
    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.

    Quote Originally Posted by clegs View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #27
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #28
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,614
    Quote Originally Posted by iMalc View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #29
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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.
    Last edited by iMalc; 12-05-2007 at 11:30 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #30
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    You didn't offend me iMalc - I just get punchy when I have been up this many hours and not making headway on these cursive recursives!

    That should be my login C++Legs! It is actually all of my initials!

Page 2 of 7 FirstFirst 1234567 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21