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. Here is what I wrote:

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 it works great, but since it's a little ugly, I wondered if there is a better way. If anyone has any thoughts / alternatives / syntactic sugar to share, that would be really appreciated!

Ps If you say "use Lisp" you won nothing (but respect). I want to know if this can be done to look good in Java.

* and how much do I handle recursion

Answer 1

2 improvements:

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

• no need to specify 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)); } } 

Run recursive(ints, 0) with recursive(ints, 0) .

Answer 2

Here's how I can make the recursive method more enjoyable:

  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 an expensive copy of the array and works for an empty input array. You can implement an additional overloaded method with two parameters only for the same signature as the iterative function:

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

Answer 3

You could pass the current index as a parameter, rather than copy almost the entire array every time, or you could use the split and win approach.

Answer 4

 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 5

... to see how well Java handles recursion

The simple answer is: Java cannot handle recursion. In particular, the Sun java and JVM Hotspot compilers do not implement tail call recursion optimization, so intensive recursion algorithms can easily consume a lot of stack space.

However, I saw articles that said the IBM JVMs support this optimization. And I saw a letter from some guy not related to the Sun who said that he was adding it as an experimental extension of Hotspot as a draft dissertation.

Answer 6

Here's a small change showing how Linked Lists are often a little nicer for recursion, where "better" means "less parameters in the method signature"

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

Answer 7

Your recursive code uses System.arrayCopy , but your iterative code does not, so your microbenchmark will not be exact. As mentioned above, you can clear this code with Math.min and use the array index instead of what you had in the queue.

Answer 8

 public class Maximum { /** * Just adapted the iterative approach of finding maximum and formed a recursive function */ public static int max(int[] arr,int n,int m) { if(m < arr[n]) { m = arr[n]; return max(arr,n - 1,m); } return m; } public static void main(String[] args) { int[] arr = {1,2,3,4,5,10,203,2,244,245,1000,55000,2223}; int max1 = max(arr,arr.length-1,arr[0]); System.out.println("Max: "+ max1); } } 

Answer 9

In fact, I have a pre class that I set to find the largest integer of any set of values. You can put this class in your project and just use it in any class:

  System.out.println(figures.getLargest(8,6,12,9,120)); 

This will return the value "120" and place it in the output file. Here is the source code of the method if you are interested in using it:

 public class figures { public static int getLargest(int...f) { int[] score = new int[f.length]; int largest=0; for(int x=0;x<f.length;x++) { for(int z=0;z<f.length;z++) { if(f[x]>=f[z]) { score[x]++; }else if(f[x]<f[z]) { }else { continue; } if(z>=f.length) { z=0; break; } } } for(int fg=0;fg<f.length;fg++) { if(score[fg]==f.length) { largest = f[fg]; } } return largest; } } 

Answer 10

Below is an example of the code given by my Java professor, Professor Penn Wu, in one of his lectures. Hope this helps.

  import java.util.Random; 


 public class Recursion 

 { 

  static int s = 0; 


  public static Double max (Double [] d, int n, Double max) 

  { 

   if (n == 0) {return max;} 

   else 

   { 


    if (d [n]> max) 

    { 

     max = d [n]; 

    } 


    return max (d, n-1, max); 


   } 

  } 


  public static void main (String [] args) 

  { 

   Random rn = new Random (); 

   Double [] d = new Double [15]; 


   for (int i = 0; i
   { 

    d [i] = rn.nextDouble (); 

    System.out.println (d [i]); 

   } 


   System.out.print ("\ nMax:" + max (d, d.length-1, d [0])); 

  } 

 } 

Answer 11

Here is my alternative

 public class recursion { public static int max( int[] n, int index ) { if(index == n.length-1) // If it simple, solve it immediately: return n[index]; // when there only one number, return it if(max(n, index+1) > n [index]) // is one number bigger than n? return max(n, index+1); // return the rest, which contains that bigger number return n[index]; // if not, return n which must be the biggest number then } public static void main(String[] args) { int[] n = {100, 3, 5, 1, 2, 10, 2, 15, -1, 20, -1203}; // just some numbers for testing System.out.println(max(n,0)); } }