Finding a max int value in an array recursive method

Question

I need help with creating a recursive method that find the max value in a vector. The method should have the following signature:

public int max(int[] v)

And use a private helping method.

Here's the method that I'm trying to use:

private int biggest(int a, int b){
    if(a > b){
        return a;
    }
    else{
        return b;
    }
}

public int maxRecursive(int[] v){
    if(v.length > 1){
        return biggest(v[0], maxRecursive(Arrays.copyOfRange(v, 1, v.length - 1)));
    }
    else{
        return v[0];
    }
}

However, all this seem to do is return the middle value of a array. Ex: If the array is `{1,2,3,5,6,7,8} the method returns 5.

you say it has to be found in a Vector, but your code shows you searching through a primitive array. Which is it? Also, why would you do this recursively, that makes no sense. Just do a straight linear run. — Mike 'Pomax' Kamermans
– Mike 'Pomax' Kamermans, Commented Nov 6, 2014 at 17:03
I'm taking a programming class, this is one of the tasks. Managed to create a iterative one but I'm stuck on the recursive method. — Pontus Brink
– Pontus Brink, Commented Nov 6, 2014 at 17:12
@PontusBrink that still doesn't explain which data structure you're using. Is it a Vector, or a plain old int array? (please edit the question to not mention the one you're not using) — Mike 'Pomax' Kamermans
– Mike 'Pomax' Kamermans, Commented Nov 6, 2014 at 17:17

Vivin Paliath · Accepted Answer · 2014-11-06 17:21:01Z

0

You have an off-by-one error, because you're using copyOfRange wrong. It should be:

maxRecursive(Arrays.copyOfRange(v, 1, v.length));

This is because the to argument is exclusive. So with your to being v.length - 1, the array only ends up looking at everything from 1 to the element before the last element.

When in doubt, read the Javadocs.

answered Nov 6, 2014 at 17:21

Vivin Paliath

95.8k42 gold badges230 silver badges302 bronze badges

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

Comments

chiastic-security · Accepted Answer · 2014-11-06 17:18:55Z

You'd be better off having a method that finds the biggest in the array up to a certain index:

public static int findMax(int[] arr, int lastPos) {
    if (lastPos==0)
        return arr[lastPos];
    else
        return biggest(arr[lastPos], findMax(arr, lastPos-1));
}

and then the biggest is

findMax(arr, arr.length-1);

This avoids all the array copying, which is rather expensive. Your code does a lot of copying, which will make it inefficient for large arrays. In this version, you pass the same array around, but as a reference; and you tell the method how far it's allowed to go in considering the array.

The key observation is that the maximum element of an array is either the last element, or the maximum of the array excluding the last element. This is essentially the same as your idea, where you're starting from the beginning; it just makes the termination case a little easier to write and to understand.

Ordous · Accepted Answer · 2014-11-06 17:19:12Z

0

Straight from the Javadoc for the method you're using (Arrays.copyOfRange):

original - the array from which a range is to be copied

from - the initial index of the range to be copied, inclusive

to - the final index of the range to be copied, exclusive. (This index may lie outside the array.)

Emphasis mine.

answered Nov 6, 2014 at 17:19

Ordous

3,89417 silver badges25 bronze badges

Comments

BlackBlaze · Accepted Answer · 2014-11-06 17:28:37Z

0

You must change the method maxRecursive

public int maxRecursive(int[] v){
    if(v.length > 1){
        return biggest(v[0], maxRecursive(Arrays.copyOfRange(v, 1, v.length)));
    }
    else{
        return v[0];
    }
}

edited Nov 6, 2014 at 17:28

answered Nov 6, 2014 at 17:22

BlackBlaze

2542 silver badges10 bronze badges

Collectives™ on Stack Overflow

Finding a max int value in an array recursive method

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related