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

Question

我决定递归地实现一个非常简单的程序，以查看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); 
    } 
} 

而且工作正常，但因为它有点难看，我想知道是否有更好的方法。如果任何人有任何想法/替代品/语法糖分享，这将非常感激！

P.s.如果你说“使用Lisp”，你就赢不了什么（但是尊重）。我想知道这是否可以在Java中看起来不错。

*以及效果如何我手柄递归

Answer 1

2倍的改进：

• 没有阵列的拷贝（只是使用偏移）

• 没有必要给当前的最大

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

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

Answer 2

你可以通过当前指数作为参数，而不是每次都几乎复制整个数组或者你可以使用分而治之的办法。

Answer 3

以下是我可能使递归方法看起来更漂亮：

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

这就避免了昂贵的阵列复制，并适用于空的输入数组。可在仅具有两个参数执行附加重载的方法为相同的签名迭代函数：

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

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

您的递归代码使用System.arrayCopy，但您的迭代代码不会执行此操作，因此您的microbenchmark不会准确。正如其他人所提到的，您可以使用Math.min并使用数组索引而不是类似队列的方法来清理该代码。

Answer 6

...去看看的Java如何处理递归

简单的答案是，Java不处理递归很好。具体而言，Sun Java编译器和Hotspot JVM不实现尾调用递归优化，因此递归密集型算法可以轻松消耗大量堆栈空间。

但是，我看到有文章说IBM的JVMs 做支持这种优化。我看到一些非Sun人的电子邮件，他说他将它作为一个实验性的Hotspot扩展程序添加为论文项目。

Answer 7

这里的展示链表怎么常常是递归的，这里的“更好”是指“在方法签名参数少”

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

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

其实我有一个预发类更好一点一定的变化，我设置为找到任何一组值的最大整数。你可以把这个类到你的项目，只是使用它在任何类，像这样：

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

这将返回值“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; 
    } 
} 

Answer 10

以下是他的一次演讲中通过我的Java讲师，宾夕法尼亚吴教授，给出一个示例代码。希望能帮助到你。

 
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

这里是我的替代

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