Thread: Recursion Revisited again, and again!

  1. #31
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    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.

  2. #32
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Elysia View Post
    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.
    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"

  3. #33
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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. #34
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    So what you both are saying now has me totally confused!

  5. #35
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Why don't you post the original algorithm? The original code you made into a recursive loop?
    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.

  6. #36
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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. #37
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Wow! I decided to type that up before you asked then posted it and SPOOKY! You asked for it!

  8. #38
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #39
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    Last edited by iMalc; 12-05-2007 at 03:05 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"

  10. #40
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    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.

  11. #41
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Ok! I will try it again.
    I probably won't see my bed tonight!
    Oh well, won't be the first time!

  12. #42
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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. #43
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    It's still 10AM here, so I have plenty of time
    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. #44
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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. #45
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Mats said two parameters passed to binarySearchImpl - first and last, but I actually need three right, item, first and last!

Popular pages Recent additions subscribe to a feed