java 通过递归找到数组中最大的正整数

Finding the largest positive int in an array by recursion

提问by Rob Grant

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:

我决定递归地实现一个非常简单的程序，看看 Java 处理递归的情况如何*，结果有点短。这就是我最终写的：

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.

Ps 如果你说“使用 Lisp”，你什么也得不到（但尊重）。我想知道这是否可以在Java 中看起来不错。

*and how well Ihandle recursion

*以及我如何处理递归

回答by Greg Hewgill

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

回答by Jerome

2 improvements:

2 改进：

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

• 没有数组的副本（仅使用偏移量）

• 无需给出当前最大值

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

以 开始递归recursive(ints, 0)。

回答by ggf31416

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.

您可以将当前索引作为参数传递，而不是每次都复制几乎整个数组，或者您可以使用分而治之的方法。

回答by cletus

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

回答by Stephen C

... to see how well Java handles recursion

... 看看 Java 处理递归的效果如何

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.

简单的答案是 Java 不能很好地处理递归。具体来说，Sun Java 编译器和 Hotspot JVM 没有实现尾调用递归优化，因此递归密集型算法很容易消耗大量堆栈空间。

However, I have seen articles that say that IBM's JVMs dosupport 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.

但是，我看到一些文章说 IBM 的 JVM确实支持这种优化。我看到一些非 Sun 人员的电子邮件，他说他将它作为一个实验性的热点扩展添加为论文项目。

回答by Peter Recore

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

回答by Kalel314

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

回答by JeremyF

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:

这将返回值“120”并将其放入输出中。如果您有兴趣使用它，这里是方法源代码：

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

回答by JavaStudent

The following is a sample code given by my Java instructor, Professor Penn Wu, in one of his lectures. Hope it helps.

以下是我的 Java 讲师 Penn Wu 教授在他的一次讲座中给出的示例代码。希望能帮助到你。

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

 }

}

回答by Tschaeggaer

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