Thread: 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

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.

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.

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]  ?