Finding Max value in an array using recursion

Question

For one of the questions i was asked to solve, I found the max value of an array using a for loop, so i tried to find it using recursion and this is what I came up with:

public static int findMax(int[] a, int head, int last) {

    int max = 0;
    if (head == last) {
        return a[head];
    } else if (a[head] < a[last]) {
        return findMax(a, head + 1, last);
    } else {
        return a[head];
    }
}

So it works fine and gets the max value, but my question is : is it ok to have for the base case return a[head] and for the case when the value at the head is > the value at last?

Answer 1

I would solve this by dividing the array in to the half on each recursive call.

 findMax(int[] data, int a, int b)

where a and b are array indices.

The stop condition is when b - a <= 1, then they are neighbours and the max is max(a,b);

The initial call:

 findMax(int[] data, int 0, data.length -1);

This reduces the maximum recursion depth from N to log2(N).
But the search effort still stays O(N).

This would result in

int findMax(int[] data, int a, int b) {
   if (b - a <= 1) {
     return Math.max(data[a], data[b]);
   } else {
     int mid = (a+b) /2; // this can overflow for values near Integer.Max: can be solved by a + (b-a) / 2; 
     int leftMax =  findMax(a, mid);
     int rightMax = findMax(mid +1, b);
     return Math.max(leftMax, rightMax);
   }
}

Answer 2

You could just as easily do it with only one counter, just the index of the value you want to compare this time:

public static int findMax(int[] a, int index) {
    if (index > 0) {
        return Math.max(a[index], findMax(a, index-1))
    } else {
        return a[0];
    }
}

This much better shows what is going on, and uses the default "recursion" layout, e.g. with a common base step. Initial call is by doing findMax(a, a.length-1).

Answer 3

It's actually much simpler than that. The base case is if you've reached the end of the array (the 'else' part of the ternary control block below). Otherwise you return the max of the current and the recursive call.

public static int findMax(int[] a) {
    return findMax(a, 0);
}
private static int findMax(int[] a, int i) {
    return i < a.length
           ? Math.max(a[i], findMax(a, i + 1))
           : Integer.MIN_VALUE;
}

At each element, you return the larger of the current element, and all of the elements with a greater index. Integer.MIN_VALUE will be returned only on empty arrays. This runs in linear time.