# Thread: Help with Binary recursive method to find the largest integer

1. Member
Join Date
Oct 2010
Posts
12
Rep Power
0

## Help with Binary recursive method to find the largest integer

The program like the title says is supposed to return the largest integer value in an user-inputted integer array, using binary recursion.
And in the case of an empty array, return Integer.MIN_VALUE.

The program compiles fine, but would always return a "java.lang.StackOverflowError".
I am thinking maybe I got the logic of the code wrong or something.
Below is my code, thanks for helping!!

Java Code:
```	public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub

int n=0, i; //n will store the user input for the number of integers
//it is set to its default value 0
//i will serve the purpose of a counter
int[] array; //creating a double array

//The line below creates a reference to a new Scanner object
// called "sc". It reads lines from standard input one at a time.
Scanner sc = new Scanner (System.in);

boolean checkException = false;//creates a boolean variable checkException
//and sets it to its default value false

do {
System.out.print ("How many integers would you like to enter? ");
try {
n = sc.nextInt();	// stores the next integer typed by the user in n using Scanner sc
checkException = true;//sets the boolean value to true, will cause
//the do-while loop to exit
}
catch (InputMismatchException e)//catch values that are not integers
{
System.out.println("This is not a correct integer, please try again.");//error message
sc.next(); //clears Scanner sc for next input
checkException = false;//sets boolean value to false, continues the loop
}
catch(ArrayIndexOutOfBoundsException a)//catches an array that has been accessed with an
//illegal index, either negative or greater than or
//equal to the size of the array
{
System.out.println("This is not a correct integer, please try again.");
sc.next();//clears Scanner sc for further input
checkException = false;
}
array = new int[n]; //declares the array variable array, giving it n elements

} while (checkException == false); //remains in loop as long as the boolean variable is false

checkException = false;

for (i=0; i<array.length; i++)
{
do {
try {
array[i]= sc.nextInt();//stores the user inputs into the indexed array elements
checkException = true;
}
catch (InputMismatchException e)//catches non-integer values and display the error message
{
System.out.println("This is not a correct integer, please try again.");
sc.next();
}
} while (checkException == false);
}
findMaxInt(array);

}
public static void findMaxInt (int [] array) {

findMaxInt(array, 0, array.length-1);

}

public static int findMaxInt (int []array, int start, int end){

if (array.length==0)
System.out.println(Integer.MIN_VALUE);

if (start>end)
return array[start];

int mid= (start+end)/2;

if (findMaxInt(array, start, mid)>findMaxInt(array, mid+1, end))
{
return findMaxInt(array, start, mid);
}
else
{
return findMaxInt(array, mid+1, end);
}

}```

2. Member
Join Date
Oct 2010
Posts
12
Rep Power
0
Originally Posted by Eranga
could you please post the complete error message here to see?
Java Code:
```How many integers would you like to enter? 4
1
2
3
4
at BinaryRecursiveFindMax.findMaxInt(BinaryRecursiveFindMax.java:102)
at BinaryRecursiveFindMax.findMaxInt(BinaryRecursiveFindMax.java:102)
at BinaryRecursiveFindMax.findMaxInt(BinaryRecursiveFindMax.java:102)[/COLOR]```
and so on

3. If you carefully look at the complete start trace then you can find the line of your code that cause this error. Can't you find that?

However it's difficult to track the stack over flow errors easily.

4. Revisit this recursive invoke.

Java Code:
```if (findMaxInt(array, start, mid)>findMaxInt(array, mid+1, end))
{
return findMaxInt(array, start, mid);
}```
take a piece of paper and write the logic here. Start with the simple step, take two numbers and think what happen here. You comes with the endless condition here and end up with the stack overflow.

Note that, these kind of error may cause lots of issues, not only on your application, may be on other applications which are running at the moment.

5. Originally Posted by flyingcurry
Java Code:
```public static int findMaxInt (int []array, int start, int end){

if (array.length==0)
System.out.println(Integer.MIN_VALUE);

if (start>end)
return array[start];

int mid= (start+end)/2;

if (findMaxInt(array, start, mid)>findMaxInt(array, mid+1, end))
{
return findMaxInt(array, start, mid);
}
else
{
return findMaxInt(array, mid+1, end);
}

}```
The length of the array never changes no matter what you do with the values of start and/or end; if it wasn't zero it won't become zero and you'll recurse all the way down until the stack overflows.

kind regards,

Jos

6. Member
Join Date
Oct 2010
Posts
12
Rep Power
0
I changed it up a little bit, and made a call table, and realized that i should have changed "else if (start>end)" to "else if (start>=end)". It seems to work fine now. Thanks for your help!

Java Code:
```public static int findMaxInt (int []array, int start, int end){

if (array.length==0)
System.out.println(Integer.MIN_VALUE);
else if (start>=end)
return array[start];
else if ((end-start)==1){
if (array[start]>array[end])
{
return array[start];
}
else
return array[end];
}
int curmax1, curmax2;

int mid= (start+end)/2;

curmax1=findMaxInt(array, start, mid);
curmax2=findMaxInt(array, mid+1, end);

if (curmax1>curmax2)
return curmax1;
else
return curmax2;
}```
Last edited by flyingcurry; 10-31-2010 at 04:15 PM.

7. Member
Join Date
Oct 2010
Posts
12
Rep Power
0
I just tried inputting 0 as the array length. And it just gave me a stackoverflow.

-2147483648
-2147483648
at sun.nio.cs.SingleByteEncoder.encodeArrayLoop(Singl eByteEncoder.java:95)
at sun.nio.cs.SingleByteEncoder.encodeLoop(SingleByte Encoder.java:134)
at java.nio.charset.CharsetEncoder.encode(CharsetEnco der.java:544)
at sun.nio.cs.StreamEncoder\$CharsetSE.implWrite(Strea mEncoder.java:384)
at sun.nio.cs.StreamEncoder.write(StreamEncoder.java: 136)
at java.io.OutputStreamWriter.write(OutputStreamWrite r.java:191)
at java.io.BufferedWriter.flushBuffer(BufferedWriter. java:111)

I don't know how else to return the "Integer.MIN_VALUE"， it's required in the assignment to return this when an array is empty.

8. Oh dear, why all that fiddling with the index? Consider this: let lo be the lowest index in the array to consider and let hi be the index of the rightmost number we don't consider. When we start the algorithm we have lo= 0 and hi= array.length.

The maximum value is either in the range [lo, mid) or in the range [mid, hi) where mid= (lo+hi)/2, i.e. the index of the element near the middle. If lo >= hi there are no elements to consider and if lo == hi-1 there's only one element in the array to consider so it is the maximum value of the array in that range.

All this sort of naturally translates to:

Java Code:
```private static int max(int[] a, int lo, int hi) {

if (lo >= hi) return Integer.MIN_VALUE;
if (lo == hi-1) return a[lo];
int mid= (lo+hi)/2;
return Math.max(max(a, lo, mid), max(a, mid, hi));
}```
kind regards,

Jos

9. Member
Join Date
Oct 2010
Posts
12
Rep Power
0
Oh wow, yes,a much simpler interpretation. I have some questions though,
1. why does is it if (lo == hi-1) return a[lo];? how do we know that array[lo] will be the larger one?

2. Why is it "return Math.max(max(a, lo, mid), max(a, mid, hi));"
and not "return Math.max(max(a, lo, mid), max(a, mid+1, hi));"

10. Originally Posted by flyingcurry
Oh wow, yes,a much simpler interpretation. I have some questions though,
1. why does is it if (lo == hi-1) return a[lo];? how do we know that array[lo] will be the larger one?

2. Why is it "return Math.max(max(a, lo, mid), max(a, mid, hi));"
and not "return Math.max(max(a, lo, mid), max(a, mid+1, hi));"
1) if lo == hi-1 we only consider one element and the maximum of an array with one element is just that element.

2) We consider all elements starting from lo (inclusive) up to hi (exclusive) so the left part of the array is [lo, mid) and the right part is [mid, hi) (pay attention to the different brackets).

kind regards,

Jos

11. Member
Join Date
Oct 2010
Posts
12
Rep Power
0