Getting the largest element in an array using recursion

Question

Any suggestions on how to make this code more efficient?

import java.util.Scanner;
public class RecursionLargestInArray 
{ 
public static void main (String[] args) 
{ 
    int max = -999; 
    Scanner scan = new Scanner (System.in); 
    System.out.print("Enter the size of the array: "); 
    int arraySize = scan.nextInt(); 
    int[] myArray = new int[arraySize]; 
    System.out.print("Enter the " + arraySize + " values of the array: "); 
    for (int i = 0; i < myArray.length; i++) 
        myArray[i] = scan.nextInt(); 
    for (int i = 0; i < myArray.length; i++) 
        System.out.println(myArray[i]); 
    System.out.println("In the array entered, the larget value is " 
                        + getLargest(myArray, max) + "."); 
} 

public static int getLargest(int[] myArray, int max) 
{     
    int i = 0, j = 0, tempmax = 0; 
    if (myArray.length == 1) 
    { 
        return myArray[0] > max ? myArray[0] : max; 
    } 
    else if (max < myArray[i]) 
    { 
        max = myArray[i]; 
        int[] tempArray = new int[myArray.length-1]; 
        for (i = 1; i < myArray.length; i++) 
        { 
            tempArray[j] = myArray[i]; 
            j++; 
        } 
        tempmax = getLargest(tempArray, max); 
        return tempmax; 
    } 
    else
    { 
        int[] tempArray = new int[myArray.length-1]; 
        for (i = 1; i < myArray.length; i++) 
        { 
            tempArray[j] = myArray[i]; 
            j++; 
        } 
        tempmax = getLargest(tempArray, max); 
        return tempmax; 
    } 
} 
}

Answer 1

I would use a helper function, and I would avoid copying the array (using indices instead):

public static int getLargest(int ... myArray) {
    return getLargest(myArray, 0, myArray.length);
}

private static int getLargest(int[] myArray, int from, int to) {
    if(from == to) {
        throw new IllegalArgumentException("empty array");
    } else if (from + 1 == to) {
        return myArray[from];
    } else {
        int middle = (from + to)  / 2;
        return Math.max(getLargest(myArray, from, middle),
                        getLargest(myArray, middle, to));
    }
}

Using varargs int ... instead of an array int[] for the argument makes it more flexible, e.g. better testable.

In case you really want to copy the array, use System.arraycopy, which is much faster than looping through.

Answer 2

This is a situation where pointers in C would be useful (or tail recursion in a functional language), but we'll work with what we have. Since this looks like homework, I'll try to guide you to a solution instead of just giving it.

Creating a new array for each recursion is terribly inefficient. You can do it inline, just pass an index to the position you're currently at in the array.

I think that should be enough, add a comment if you need more.

Edit: You don't even need the max as an argument.

Answer 3

1. If you are using a return inside a condition, do you need to brace the following code inside an else? (example: first if of the getLargest() method)
2. The second and third blocks of code in the getLargest() method repeat a lot of code, I am sure that you can figure out a good way to avoid this repetition;
3. @Kevin makes a very good point, do you really need to create a new array in every iteration?
4. What if the user answers -1 to the first question?
5. What would your program answer to a user inputing 3 and then -1020, -1050, -1013?

Answer 4

Here's small Java program to find the max element in an array recursively

public class TestProgram {
    private int[] a = { 3, 5, 2, 8, 4, 9 };

    public static void main(String[] args) {
        TestProgram p = new TestProgram();
        int result = p.findMax(0);
        System.out.printf("Max element = %d", result);
    }

    public int findMax(int i) {
        // the anchor of the recursive method
        if (i == a.length)
            return Integer.MIN_VALUE;

        return Math.max(a[i], findMax(i + 1));
    }
}