CSC 326 - Prof. Bernie Domanski - Recursion

Minimum's and Maximum's

This is a nice, short program meant to illustrate the power of recursion … and along the way, it may confound and confuse you too!

Create an array of an odd number of elements … like 31.  Fill the array in an unsorted manner with integer numbers. You don't have to get fancy and read in values from a file or anything like that. Just initialize the array with numbers.

Then, from your main program, call on a maxmin function. This function should accept as parameters the following:

• Lo - the index of the starting element of a sub-array of the whole array
• Hi - the index of the ending element of the sub-array
• Min - will contain the value of the smallest element in the sub-array
• Max - will contain the value of the largest element in the sub-array

Thus, when called from the main program with lo equal to 0 and hi equal to the upper index limit of the entire array (e.g. 30), minmax will return the minimum and the maximum of the entire array.

No, you cannot sequentially search the array once for a maximum and once for a minimum! Minmax should first check if the sub-array being searched is a trivial one (that is, containing only 1 or 2 elements in all). If trivial, simply return the minimum and the maximum.

But if it's not trivial, then, from minmax, split the subarray into 2 logical halves. Then call on minmax two times: once to find the minimum and maximum of the lower logical half, and again to find the minimum and maximum of the upper logical half. With these 2 pairs of minimums and maximums, you should be able to compare them to each other, and return the true minimum and maximum to the calling program.

Be careful … 'cause if your logic is broken, you could easily go into an infinite loop that is calling minmax over and over and … !

Comments count;
Neatness counts;
Due Thursday April 17th;
Lateness means death.
Only in-class presentation will be accepted.

Last updated by DrB on Friday, April 04, 2008 04:13 PM