1. ## Recursion

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.

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.

Well the figure on p84 looks pretty much like

MaxArray(<1,6,8,3>)
return max(maxArray(<1,6>) , maxArray(<8,3>)

| |
maxArray(<1,6>) maxArray(<8,3>)
return max(<1>), maxArray(<6>) return(maxArray<8>),maxArray(<3>)
| | | |
maxArray(<1>) maxArray(<6>) maxArray(<8>), maxArray(<3>)
return 1 return 6 return 8 return 3

Any ideas ?Any help is appreciated

2. That pretty much describes exactly what you're supposed to do, doesn't it?

What's the actual question? What are you having difficulty with?

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

else

return maxArray[i+1]

Am I on the right track?

4. Looks to me like the max function just returns the max of two values. The function that would do the recursion is maxArray. If you do have to do recursion, remember that you must have a base case. The obvious choice here is when there are no more values in the array to compare. At that point, the maximum value (that you have been keeping track of) can be returned. I guess my prototype would look something like:

Code:
`int maxArray(int *array, int size);`
Then, for the base case, inside the function:
Code:
```if (size == 1)
return MAX(cur_max, array[0]);```
I'll leave the other case to you, where you actually keep track of the maximum value and compare successive elements in the array.

5. Originally Posted by MacNilly
...The obvious choice here is when there are no more values in the array to compare....

Then, for the base case, inside the function:
Code:
```if (size == 1)
return MAX(cur_max, array[0]);```
Err, I think you mean the obvious choice is when there is one element in the array:

Code:
```if ( size == 1 )
return array[0];```
since that value *has* to be the max.

6. Im getting the idea, but how do u split an array in half?
Code:
`  like array[]={1,2,3,4}  to  array[]={1.2} and array[]={3,4]  ?`

7. You could keep track of the start and end of a range, e.g., by using a pair of indices. So, with two such pairs, you would have two "halves" of the array.