Join 118,654 C++ Programmers for FREE! Ask your question and get quick answers from experts. There are 896 online right now! We've got more than 500 tutorials and 2,000 snippets. Join and find out why Dream.In.Code is the #1 programming help community on the internet! Registration is fast and FREE... Join Now!
I'm having a problem understanding recursion. I understand that it is like a continous loop that breaks down your big problem into little ones, but implementing it is a prob. I am taking an online C++ course (that probably a problem in itself) that gave a homework assignment that involves recursion. Im not looking for someone to do my homeowork, just a push in the right direction for a start on how to tackle this problem.
[B]2.7 Implement maxarray, discussed in the section “Finding the Largest Item in an Array,” as a recursive C++ function. Note the call tree on page 84 uses a helper function named max. What does the name max imply as the purpose of the function? You will write this helper function.
It seems an overcomplicated way to learn recursion, there's much simpler recursive problems.
In Pseudocode I would do it this way:
CODE
//Double can be replaced by anything comparable) double max(double[] array){ if the array size is 2 or larger{ run the max function on each half of the array and return the bigger result } If there's 1 value{ return that value } }
I think that's right, It's similar to the way a Merge sort breaks up the array for comparisons (In my mind anyway), it splits the array continually until it's comparing single elements before re forming the data on the way back up the tree.
I don't think C++ has a way to get Array size which makes it just a bit more complicated.
This post has been edited by Mallstrop: 1 Jul, 2008 - 11:59 AM
When teachers ask you to write the helper function, they want you to actually write the usable function
So what this question is asking for is to use the helper function to recursively produce the splits in the array? ex. Like Array[]={1,5,7,3} , how would you split this up?
Also, in recursion, i thought u had to use the function within itself? With the code that you wrote below double max takes in the array and asks if the array is 2 or more? if it does then it repeats the same function again? like double max( maxArray[]) { if (maxArray[] > 2 ) How would you do this? // divide array in half
int i=0;
if (maxArray[i] > maxArray[i+1]) return maxArray[i]
Almost, every time you call the maxArray function, you continually set your variable "i" to 0, you have the basic idea. The best way to understand recursion is to see great examples of it. Look for recursion examples here as well as wikipedia for instance.
The array is actually a little bit a red herring in the problem you're given.
Here's a hint. Your function should look like this:
CODE
int MaxArray(int [] list, int begin, int end) { ...
As noted, getting the length of arrays is a pain in C++. In C, you often pass the size of a array for that reason. Also, slicing arrays, creating smaller ones from larger, is also a pretty manual process.
Now, reconsider your problem, thinking of where the cuts are:
Here's my getMax function if you've still not worked it out.
Not guaranteed to be the best answer but it works according to my testing.
CODE
//Recursive get Max for an Array //start is where to start looking //end is where to finnish looking int getMax(int val[], int start, int end){
//if the array size is 1 (1 element in the set) return that value if ((end - start) == 1){ return val[start]; }
//if the size is 2 or more cut the array down until there's just 1 element //and it qualifies for the statement above.
//Find the middle point int middle = (start + end) /2;
//Run getMax on the first half of the data int first = getMax(val, start, middle); //Run getMax on the second half int second = getMax(val, middle, end); //Compare the 2 results and return the largest. if (first > second){ return first; } else{ return second; } }
I should add that it can be overloaded with:
CODE
int getMax(int val[], int size){ return getMax(val, 0, size); }
This post has been edited by Mallstrop: 3 Jul, 2008 - 08:02 AM
Wow, its gonna be a little bit before i can digest this code. i so have to read this a few times to understand every thing.
QUOTE(Mallstrop @ 3 Jul, 2008 - 08:01 AM)
Here's my getMax function if you've still not worked it out.
Not guaranteed to be the best answer but it works according to my testing.
CODE
//Recursive get Max for an Array //start is where to start looking //end is where to finnish looking int getMax(int val[], int start, int end){
//if the array size is 1 (1 element in the set) return that value if ((end - start) == 1){ return val[start]; }
//if the size is 2 or more cut the array down until there's just 1 element //and it qualifies for the statement above.
//Find the middle point int middle = (start + end) /2;
//Run getMax on the first half of the data int first = getMax(val, start, middle); //Run getMax on the second half int second = getMax(val, middle, end); //Compare the 2 results and return the largest. if (first > second){ return first; } else{ return second; } }
I should add that it can be overloaded with:
CODE
int getMax(int val[], int size){ return getMax(val, 0, size); }
Our result should be 4. We can now see what's going on. There are two distinct errors here, one returning bad values, the other searching in a strange way. These are very common error types.
First, the search.
cpp
int middle = (start + end) /2; int first = getMax(val, start, middle); int second = getMax(val, middle, end);
We seem to be hitting the middle in both calls. If we change int second = getMax(val, middle, end); to int second = getMax(val, middle+1, end);, our search get's much shorter:
It's what we expected. One bug down, still not getting back the value we want. Here, the error a little subtle. This if ((end - start) == 1){ return val[start]; } always returns first of the pair, it should be doing a compare! We can fix it like so:
cpp
if ((end - start) == 1){ int first = val[start]; int second = val[end]; if (first > second){ return first; } else { return second; } }
Output:
CODE
getMax: 0,3 getMax: 0,1 getMax: 2,3 result = 4
Success! Only, our code now looks a little redundant. Time to refactor! Here's a final working copy:
cpp
int getMax(int val[], int start, int end){ int first, second; if ((end - start) == 1){ first = val[start]; second = val[end]; } else { int middle = (start + end) /2; first = getMax(val, start, middle); second = getMax(val, middle+1, end); } return (first > second) ? first : second; }
That's it. Apologies to Mallstrop for abusing the offered code. However, it seemed a good place to start and maybe show what is going on.
LOL, in a good example if no one's code is perfect, the above example still has a very serious bug. Put a the trace back in and try an odd count list. You'll find yourself in an infinite loop at "getMax: 2,2". In keeping with the site, this came to me in sleep.
Here's the code that works. I left the trace, you can try it without the odd stopper and see it spin.
cpp
int getMax(int val[], int start, int end){ int first, second; cout << "getMax: " << start << "," << end << endl; int diff = end - start; if (diff<1) { return val[start]; } else if (diff==1) { first = val[start]; second = val[end]; } else { int middle = (start + end) /2; first = getMax(val, start, middle); second = getMax(val, middle+1, end); } return (first > second) ? first : second; }
I changed my code slightly to add a print out of what's being compared and that simpler if statement.
CODE
int getMax(int val[], int start, int end){ if ((end - start) == 1){ return val[start]; }
int middle = (start + end) /2; int first = getMax(val, start, middle); int second = getMax(val, middle, end);
cout << "Comparing : " << first << " to " << second << endl;
return (first > second) ? first : second; }
int getMax(int val[], int size){ return getMax(val, 0, size); }
called using:
CODE
int main(){ int testVals[] = {1,2,3,4,5,6,7,8}; cout << getMax(testVals, 8) << endl; }
The output it gives is:
Comparing : 1 to 2 Comparing : 3 to 4 Comparing : 2 to 4 Comparing : 5 to 6 Comparing : 7 to 8 Comparing : 6 to 8 Comparing : 4 to 8 8
which seems to be correct.
It might just be that we're taking a different approach to the problem.
End seems to point to the position after the end of the array as is seen in Iterators.
I used to use Middle and Middle+1 but it would miss out the central item of the array so I changed it to Middle and Middle which seemed to work so I didn't question it.
1 Jul, 2008 - 11:33 AM
| 