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

Recursion is not going to be as simple or efficient in Java as iteration except very rare cases. — Peter Lawrey
– Peter Lawrey, Commented Dec 31, 2009 at 13:06
Yeah, but if anyone's going to be well prepared for the space complexity of recursion, it's a Java developer :) — Rob Grant
– Rob Grant, Commented Dec 31, 2009 at 13:35
In any language, you'll always have to either copy the array, or pass indices into that array. If you mean "Lisp using a linked list", then sure, it's nicer than "Java using an array", but I think "X using a linked list" is nicer than "Y using an array" for any X and Y. (Displaced arrays in Common Lisp handle a little of the bookkeeping for you, but I don't think they really make this case much simpler.) — Ken
– Ken, Commented Jan 1, 2010 at 3:49

Greg Hewgill · Accepted Answer · 2009-12-31 09:58:39Z

10

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

answered Dec 31, 2009 at 9:58

Greg Hewgill

1.0m192 gold badges1.2k silver badges1.3k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Rob Grant Over a year ago

JOOI, is there any difference between Math.max and a ternary operator with a greater than?

Greg Hewgill Over a year ago

Yes, I find that using max() is easier to read than using the Java conditional operator for the same purpose. If there's a performance difference, you would have to measure it for your specific environment.

Ken Over a year ago

With max() you Don't have to Repeat Yourself.

Jerome · Accepted Answer · 2009-12-31 10:00:09Z

7

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).

answered Dec 31, 2009 at 10:00

Jerome

8,4572 gold badges35 silver badges41 bronze badges

2 Comments

Rob Grant Over a year ago

I actually preferred this one because its use of recursion is more legant than the winning answer, but it doesn't do some things the winner does. Thanks though :)

Jerome Over a year ago

Such as? The only difference to my eyes is the handling of an empty array which throws an exception here (good, there is no max so no good answer) vs returning an arbitrary (false) value in the winning answer.

ggf31416 · Accepted Answer · 2009-12-31 10:02:56Z

2

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.

edited Dec 31, 2009 at 10:02

answered Dec 31, 2009 at 9:57

ggf31416

3,6571 gold badge28 silver badges26 bronze badges

Comments

cletus · Accepted Answer · 2009-12-31 09:59:21Z

1

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

answered Dec 31, 2009 at 9:59

cletus

627k169 gold badges922 silver badges945 bronze badges

Comments

Stephen C · Accepted Answer · 2010-01-01 03:40:05Z

1

... 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.

answered Jan 1, 2010 at 3:40

Stephen C

723k95 gold badges849 silver badges1.3k bronze badges

1 Comment

Rob Grant Over a year ago

Apparently nothing :)

Peter Recore · Accepted Answer · 2010-01-01 05:27:12Z

1

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

answered Jan 1, 2010 at 5:27

Peter Recore

14.2k5 gold badges44 silver badges64 bronze badges

Comments

Kristopher Ives · Accepted Answer · 2009-12-31 10:50:02Z

0

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.

answered Dec 31, 2009 at 10:50

Kristopher Ives

6,1058 gold badges46 silver badges70 bronze badges

Comments

Andrew Barber · Accepted Answer · 2013-02-19 21:01:20Z

0

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

edited Feb 19, 2013 at 21:01

Andrew Barber

40.3k20 gold badges97 silver badges124 bronze badges

answered Feb 19, 2013 at 20:55

Kalel314

1

1 Comment

Andrew Barber Over a year ago

Welcome to Stack Overflow! Would you consider adding some narrative to explain why this code works, and what makes it an answer to the question? This would be very helpful to the person asking the question, and anyone else who comes along.

JeremyF · Accepted Answer · 2013-07-05 14:59:19Z

I actually have a pre made class that I setup for finding the largest integer of any set of values. You can put this class into your project and simply use it in any class like so:

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

This would return the value "120" and place it in the output. Here is the methods source code 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;
    }
}

JavaStudent · Accepted Answer · 2015-09-13 02:20:47Z

0

The following is a sample code given by my Java instructor, Professor Penn Wu, in one of his lectures. Hope it 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]));

 }

}

answered Sep 13, 2015 at 2:20

JavaStudent

1

1 Comment

filoxo Over a year ago

Welcome to SO! Please consider editing your question to include detailed explanations of why and how this code answers the question. Additionally, you may want to receive permission before posting a professor's code or his name associated with said code, just as a common courtesy.

score 0 · Accepted Answer · 2015-12-07 13:07:32Z

0

Here is my alternative

public class recursion
{
  public static int max( int[] n, int index )
  {
    if(index == n.length-1)   // If it's simple, solve it immediately:
      return n[index];        // when there's 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));
  }
}

edited Dec 7, 2015 at 13:07

answered Dec 7, 2015 at 12:11

user5649814

Collectives™ on Stack Overflow

Finding the largest positive int in an array by recursion

11 Answers 11

3 Comments

2 Comments

Comments

Comments

1 Comment

Comments

Comments

1 Comment

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

11 Answers 11

3 Comments

2 Comments

Comments

Comments

1 Comment

Comments

Comments

1 Comment

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related