# Getting the largest element in an array using recursion

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;
}
}
}

• Does it need to use recursion? In case this is homework, please tag it as such. Nov 15, 2011 at 15:25
• I wonder if you aren't expected to use the recursion on getting the user input, rather than on checking the largest value... Nov 15, 2011 at 16:15
• @Steven added. I have already handed in the assignment so is really just more for my own knowledge now Nov 15, 2011 at 16:50
• @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. Nov 15, 2011 at 16:52
• @NYCCanuck Nicely done. Nov 15, 2011 at 16:56

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.

• +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. Nov 15, 2011 at 16:19
• 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. Nov 15, 2011 at 23:11

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.

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

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));
}
}