通過遞歸找到數組中的最大正整數

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