Highest number in a array by recursive divide and conquer

Question

My code should return the highest number in a given array using a recursive divide and conquer method.

For a[1,3,2,4,6] i should return 6.

For some reason my code is StackOverflowing in the line 47

Exception in thread "main" java.lang.StackOverflowError at maiordivisaoconquista.DivideAndConquer.Highest(DivideAndConquer.java:47)

public class DivideAndConquer {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) 
{
   Scanner s = new Scanner (System.in);
   int n = s.nextInt();
   int a[] = new int [n];
   for(int i = 0; i < a.length; i++)
   {
       a[i] = s.nextInt();
   }
   int first = 0;
   int last  = a.length;
   System.out.println(Highest(a,first,last));
}

public static int Highest (int a[], int first, int last)
{

    if(first == last)
    {
        return a[first];
    }
    if (last - first == 1)
    {
        return Math.max(a[first],a[last]);
    }

    else
    {
       int middle = (first +last)/2;
       return(Math.max(Highest(a,first,last),Highest(a,middle+1,last)));
    }

 }
}

Bohemian · Accepted Answer · 2019-03-18 02:20:15Z

1

Change like this:

return(Math.max(Highest(a, first, last),   Highest(a, middle+1, last)));
                                    |
                                    |
                                    V
return(Math.max(Highest(a, first, middle), Highest(a, middle+1, last)));

Your code calls itself with the same first and last values, and so will (usually) infinitely recurse.

answered Mar 18, 2019 at 2:20

Bohemian♦

427k103 gold badges603 silver badges750 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Luiz Gabriel Ferreira Over a year ago

That will work for the infinite loop but now i got a array out of bounds in: Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5 at maiordivisaoconquista.DivideAndConquer.Highest(DivideAndConquer.java:37) at maiordivisaoconquista.DivideAndConquer.Highest(DivideAndConquer.java:47) at maiordivisaoconquista.DivideAndConquer.Highest(DivideAndConquer.java:47) at maiordivisaoconquista.DivideAndConquer.main(DivideAndConquer.java:29)

Arvind Gangam Over a year ago

in your main method you should have int last = a.length -1 ; instead of last = a.length length is number of elements in array but last element is a[length-1] hence last = a.length -1

Collectives™ on Stack Overflow

Highest number in a array by recursive divide and conquer

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related