Finding the largest positive int in an array by recursion

Question

I decided to implement a very simple program recursively, to see how well Java handles recursion*, and came up a bit short. This is what I ended up writing:

public class largestInIntArray {
  public static void main(String[] args)
  {
    // These three lines just set up an array of ints:
    int[] ints = new int[100];
    java.util.Random r = new java.util.Random();
    for(int i = 0; i < 100; i++) ints[i] = r.nextInt();

    System.out.print("Normal:"+normal(ints,-1)+" Recursive:"+recursive(ints,-1));
  }

  private static int normal(int[] input, int largest) {
    for(int i : input)
      if(i > largest) largest = i;

    return largest;
  }

  private static int recursive(int[] ints, int largest) {
    if(ints.length == 1)
      return ints[0] > largest ? ints[0] : largest;

    int[] newints = new int[ints.length - 1];
    System.arraycopy(ints, 1, newints, 0, ints.length - 1); 

    return recursive(newints, ints[0] > largest ? ints[0] : largest);
  }
}

And that works fine, but as it's a bit ugly I wondered if there was a better way. If anyone has any thoughts/alternatives/syntactic sugar to share, that'd be much appreciated!

P.s. If you say "use Lisp" you win nothing (but respect). I want to know if this can be made to look nice in Java.

*and how well I handle recursion

Answer 1

You could pass the current index as a parameter rather than copying almost the entire array each time or you could use a divide and conquer approach.

Answer 2

Here's how I might make the recursive method look nicer:

  private static int recursive(int[] ints, int largest, int start) {
    if (start == ints.length) {
      return largest;
    }
    return recursive(ints, Math.max(ints[start], largest), start + 1);
  }

This avoids the expensive array copy, and works for an empty input array. You may implement an additional overloaded method with only two parameters for the same signature as the iterative function:

  private static int recursive(int[] ints, int largest) {
    return recursive(ints, largest, 0);
  }

Answer 3

public static int max(int[] numbers) {
  int size = numbers.length;
  return max(numbers, size-1, numbers[size-1]);
}

public static int max(int[] numbers, int index, int largest) {
  largest = Math.max(largest, numbers[index]);
  return index > 0 ? max(numbers, index-1, largest) : largest;
}

Answer 4

2 improvements:

• no copy of the array (just using the offset)

• no need to give the current max

  private static int recursive(int[] ints, int offset) {
      if (ints.length - 1 == offset) {
          return ints[offset];
      } else {
          return Math.max(ints[offset], recursive(ints, offset + 1));
      }
  }
  

Start the recursion with recursive(ints, 0).

Answer 5

Your recursive code uses System.arrayCopy, but your iterative code doesn't do this, so your microbenchmark isn't going to be accurate. As others have mentioned, you can clean up that code by using Math.min and using an array index instead of the queue-like approach you had.

Answer 6

... to see how well Java handles recursion

The simple answer is that Java doesn't handle recursion well. Specifically, Sun java compilers and Hotspot JVMs do not implement tail call recursion optimization, so recursion intensive algorithms can easily consume a lot of stack space.

However, I have seen articles that say that IBM's JVMs do support this optimization. And I saw an email from some non-Sun guy who said he was adding it as an experimental Hotspot extension as a thesis project.

Answer 7

Here's a slight variation showing how Linked Lists are often a little nicer for recursion, where "nicer" means "less parameters in method signature"

  private static int recursive(LinkedList<Integer> list) {
    if (list.size() == 1){
      return list.removeFirst();
    }
    return Math.max(list.removeFirst(),recursive(list));
  }