Finding Max of an array using Recursion

Question

So it's pretty simple to find the max of an array using a for loop or a while loop, but I wanted to try it out with recursion. For some reason, the substring doesn't work - it says "cannot find symbol". Why is this? My strategy is continue subdividing and comparing the two sides until there is only one left which should be the max....am I doing it right? Thanks

   public static int max(int[] array) {

    if (array.length == 1) {
        return array[0];
    } else {
        int mid = (array.length) / 2;
        int leftmax = max(array.substring(0, mid));
        int rightmax = max(array.substring(mid, array.length));
        if (leftmax > rightmax) {
            return leftmax;
        } else {
            return rightmax;
        }

    }
}

If you wait few minutes, I will add answer with explained recursion which works. I hope you will learn from it, right now, you are not using recursion at all :). — libik
– libik, Commented Mar 24, 2014 at 16:30
@libik why do you say he is not using recursion? he is calling max() from within max(). That is recursion. — clcto
– clcto, Commented Mar 24, 2014 at 16:32

score 4 · Accepted Answer · 2014-03-24 16:34:27Z

4

You are going to want to use Arrays.copyOfRange. Substring isn't going to work on an array.

int[] firstHalf = Arrays.copyOfRange(original, 0, original.length/2);
int[] secondHalf = Arrays.copyOfRange(original, original.length/2, original.length);

I can't comment on your algorithm.

edited Mar 24, 2014 at 16:34

answered Mar 24, 2014 at 16:29

user2591612

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

Comments

clcto · Accepted Answer · 2014-03-24 16:41:26Z

1

Since array is of type int[] not String, you cannot use substring(). Instead, keep track of which indexes you are searching through. Copying the array each iteration is a waste of both space and time.

int max( int[] array ){ return max( array, 0, array.length - 1 ); }

int max( int[] array, int low, int high )
{
    if (low == high) {
        return array[low];
    } 
    else {
        int mid = (high + low) / 2;
        int leftmax = max(array, low, mid );
        int rightmax = max(array, mid, high );
        if (leftmax > rightmax) {
            return leftmax;
        } 
        else {
            return rightmax;
        }

    }
}

answered Mar 24, 2014 at 16:41

clcto

9,66823 silver badges43 bronze badges

Collectives™ on Stack Overflow

Finding Max of an array using Recursion

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related