# finding a max number via a recursive method

michael bradly

Ranch Hand

Posts: 112

posted 13 years ago

- 0

I am trying to work on a problem in which I have to find the max number in an array by dividing the array in two, then find the largest int in each half, then find the largest of the two. I understand most of the concepts, but am having trouble bringing them all together.

Here is what I think I know...

myArray (int[] anArray, first, last, maxValue)

{

// base case

if (the array only has one value)

return maxValue = anArray[0];

/* Question #1: Since I am going to have to compare two ints, do I need a second base case? i.e.:

else if (there are 2 values to compare)

if (maxLeftArray == maxRightArray)

assign to maxValue either one

else if (maxLeftArray < maxRightArray)

assign to maxValue maxRightArray

else if (maxLeft > maxRight)

assign to maxValue maxLeftArray

*/

else (find the midpoint in the array)

midpoint = (first + last)/2;

/*Question 2: How to deal with the midpoint?

For sake of argument, these values are in the array {12, 5, 6, 7, 15, 20}

Now the midpoint is [3] which is 6.

So now I have {12, 5} midpoint of 6 and {7, 15, 20}. Since I am unsure as to the merits of question 1, I'll deal with this as I understand it.

*/

myArray(int[] anArray, first, midpoint -1, maxValue)

if (midpoint > anArray[first+1])

maxLeftArray = midpoint;

// my assumption is that when there are only two

//subidexes left, the midpoint is [0] and what

//it is being compared to is [1]

else maxLeftArray = anArray[first+1];

myArray (int[] anArray, midpoint +1, last, maxValue)

if (midpoint +1 < anArray[last])

maxRightArray = anArray[last];

else maxRightArray = midpoint +1;

// or can I include the midpoint in the left side

// (int[] an Array, first, midpoint???, maxValue)

As may be evident, I am confused. Any suggestions or helpful web references would be appreciated.

Regards, Michael

[ September 05, 2002: Message edited by: michael bradly ]

Here is what I think I know...

myArray (int[] anArray, first, last, maxValue)

{

// base case

if (the array only has one value)

return maxValue = anArray[0];

/* Question #1: Since I am going to have to compare two ints, do I need a second base case? i.e.:

else if (there are 2 values to compare)

if (maxLeftArray == maxRightArray)

assign to maxValue either one

else if (maxLeftArray < maxRightArray)

assign to maxValue maxRightArray

else if (maxLeft > maxRight)

assign to maxValue maxLeftArray

*/

else (find the midpoint in the array)

midpoint = (first + last)/2;

/*Question 2: How to deal with the midpoint?

For sake of argument, these values are in the array {12, 5, 6, 7, 15, 20}

Now the midpoint is [3] which is 6.

So now I have {12, 5} midpoint of 6 and {7, 15, 20}. Since I am unsure as to the merits of question 1, I'll deal with this as I understand it.

*/

myArray(int[] anArray, first, midpoint -1, maxValue)

if (midpoint > anArray[first+1])

maxLeftArray = midpoint;

// my assumption is that when there are only two

//subidexes left, the midpoint is [0] and what

//it is being compared to is [1]

else maxLeftArray = anArray[first+1];

myArray (int[] anArray, midpoint +1, last, maxValue)

if (midpoint +1 < anArray[last])

maxRightArray = anArray[last];

else maxRightArray = midpoint +1;

// or can I include the midpoint in the left side

// (int[] an Array, first, midpoint???, maxValue)

As may be evident, I am confused. Any suggestions or helpful web references would be appreciated.

Regards, Michael

[ September 05, 2002: Message edited by: michael bradly ]

Anthony Villanueva

Ranch Hand

Posts: 1055

Norm Miller

Ranch Hand

Posts: 56

posted 13 years ago

- 0

Here's an example to study. You can see how the code keeps breaking the array in pieces about half as big as the input array. There is a test to stop when the array is only one element.

(The code breaks if you start with iA[] = {} so either don't do that or fix it.)

(If you aren't using the 1.4 release, you can omit the asserts.)

[ September 06, 2002: Message edited by: Norm Miller ]

[ September 06, 2002: Message edited by: Norm Miller ]

(The code breaks if you start with iA[] = {} so either don't do that or fix it.)

(If you aren't using the 1.4 release, you can omit the asserts.)

[ September 06, 2002: Message edited by: Norm Miller ]

[ September 06, 2002: Message edited by: Norm Miller ]

michael bradly

Ranch Hand

Posts: 112

posted 13 years ago

- 0

Thanks for the responses. The main issue is that I am taking a class in algorithms/data structures, so regardless of what inherent features the various JDK's have to deal with finding a max, I must use a recursive method to find the max.

My personal problem with such situations is that I extrapolate my thought processes as to how a computer deals with a situation, and not only do I find myself thinking too much about the problem, but I also end up thinking incorrectly as to how a computer would deals with it since a computer tends to be much more efficient than my thoughts.

Essentially the code I listed deals with how my brain is dealing with the situation and I am seeking guidance as to how a computer deals with recursive solutions in regards to finding a max number in an unsorted array.

Althought I am implementing the solution in Java, I am not so much looking for the simplest way to do it in Java, rather I am looking for a way to do it in a language netural manner so I can come to a better understanding of recursion. (Although I really want to do it in JAVA!!!)

I've had to much to drink!

Regards, Micahel

My personal problem with such situations is that I extrapolate my thought processes as to how a computer deals with a situation, and not only do I find myself thinking too much about the problem, but I also end up thinking incorrectly as to how a computer would deals with it since a computer tends to be much more efficient than my thoughts.

Essentially the code I listed deals with how my brain is dealing with the situation and I am seeking guidance as to how a computer deals with recursive solutions in regards to finding a max number in an unsorted array.

Althought I am implementing the solution in Java, I am not so much looking for the simplest way to do it in Java, rather I am looking for a way to do it in a language netural manner so I can come to a better understanding of recursion. (Although I really want to do it in JAVA!!!)

I've had to much to drink!

Regards, Micahel

It is sorta covered in the JavaRanch Style Guide. |