7
\$\begingroup\$

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; 
    } 
} 
}
\$\endgroup\$
  • \$\begingroup\$ Does it need to use recursion? In case this is homework, please tag it as such. \$\endgroup\$ – Steven Jeuris Nov 15 '11 at 15:25
  • \$\begingroup\$ I wonder if you aren't expected to use the recursion on getting the user input, rather than on checking the largest value... \$\endgroup\$ – ANeves Nov 15 '11 at 16:15
  • \$\begingroup\$ @Steven added. I have already handed in the assignment so is really just more for my own knowledge now \$\endgroup\$ – NYC Canuck Nov 15 '11 at 16:50
  • \$\begingroup\$ @ANeves The assignment is to write a recursive program to find the largest element of an array. I added the user input on my own instead of initializing arrays. \$\endgroup\$ – NYC Canuck Nov 15 '11 at 16:52
  • \$\begingroup\$ @NYCCanuck Nicely done. \$\endgroup\$ – ANeves Nov 15 '11 at 16:56
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ +0: why can't you just Math.Max(myArray[from], getLargest(myArray, from+1, to)) in that last else? I feel you're making it needlessly complex. \$\endgroup\$ – ANeves Nov 15 '11 at 16:19
  • \$\begingroup\$ Using my way you'll have a maximum call stack depth of 2*(ld n), your version would have a maximum depth of n, which could lead to an StackOverflowException for very large arrays. \$\endgroup\$ – Landei Nov 15 '11 at 23:11
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I am not sure how to just pass the index of the array position. Do you mean getLargest(tempArray[i], max);? \$\endgroup\$ – NYC Canuck Nov 15 '11 at 16:56
  • \$\begingroup\$ The signature should be int getLargest(int[] array, int currentIndex). Then call it with getLargest(array, currentIndex + 1);. \$\endgroup\$ – Kevin Nov 15 '11 at 18:08
3
\$\begingroup\$
  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?
\$\endgroup\$
1
\$\begingroup\$

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));
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.