重構這個遞歸方法？

Question

我對遞歸的想法很新，這實際上是我第一次嘗試寫遞歸方法。

我試圖實現一個遞歸函數Max，它傳遞一個數組以及一個保存數組大小以便打印最大元素的變量。

它的作品，但它只是沒有感覺正確！

我也注意到，我似乎使用static修飾符比我一般同學更多...

任何人都可以請提供任何一般提示，以及反饋，我怎麼能提高我的代碼？

public class RecursiveTry{ 

static int[] n = new int[] {1,2,4,3,3,32,100}; 
static int current = 0; 
static int maxValue = 0; 
static int SIZE = n.length; 

public static void main(String[] args){ 
    System.out.println(Max(n, SIZE)); 
} 

public static int Max(int[] n, int SIZE) { 
    if(current <= SIZE - 1){ 
     if (maxValue <= n[current]) { 
      maxValue = n[current]; 
      current++; 
      Max(n, SIZE);      
     } 
     else { 
      current++; 
      Max(n, SIZE); 
     } 
    } 
    return maxValue; 
} 

}

Answer 1

您將靜態變量用於在函數外部保持狀態將是一個難點。

一個遞歸實現一個最大的例子（）在僞功能可能是：

function Max(data, size) { 
    assert(size > 0) 
    if (size == 1) { 
     return data[0] 
    } 
    maxtail = Max(data[1..size], size-1) 
    if (data[0] > maxtail) { 
     return data[0] 
    } else { 
     return maxtail 
    } 
} 

這裏的關鍵是MAX（），在那裏你通過一切除了的第一個元素的遞歸調用，還有一個小於規模。總體思路是這個函數表示「這個數據中的最大值是第一個元素，或者是數組其餘部分的最大值，取大者」。

該實現不需要函數定義之外的靜態數據。

遞歸實現的特點之一就是所謂的「終止條件」，它可以防止遞歸永遠持續下去（或者直到出現堆棧溢出）。在上述情況下，size == 1的測試是終止條件。

Answer 2

「最大」的功能是錯誤類型的東西寫一個遞歸函數 - 你正在使用靜態值「當前」和「包括maxValue」讓你的事實函數不是一個真正的遞歸函數。

爲什麼不做一些更適合遞歸算法的東西，比如階乘？

Answer 3

首先，讓我們來關注靜態範圍問題......你的類正在定義一個對象，但從來沒有真正實例化一個對象。由於主要是靜態範圍，要做的第一件事就是獲取一個對象，然後執行它是這樣的方法：

public class RecursiveTry{ 

    private int[] n = {1,2,4,3,3,32,100}; 

    public static void main(String[] args){ 
     RecursiveTry maxObject = new RecursiveTry(); 
     System.out.println(maxObject.Max(maxObject.n, 0)); 
    } 

    public int Max(int[] n, int start) { 
     if(start == n.length - 1) { 
      return n[start]; 
     } else { 
      int maxRest = Max(n, start + 1); 
      if(n[start] > maxRest) { 
       return n[start]; 
      } 
      return maxRest; 
     } 
    } 

} 

所以，現在我們有一個名爲maxObject一個RecursiveTry對象不需要靜態範圍。我不確定使用遞歸找到最大值是否有效，因爲傳統循環方法中的迭代次數大致相當，但使用遞歸的堆棧數量較多。但對於這個例子，我會減少很多。

遞歸的優點之一是，您的狀態通常不需要在重複測試期間持久化，就像它在迭代中一樣。在這裏，我已經承認使用變量來保存起始點，因爲它傳遞一個包含除第一個項目之外的所有項目的新int []函數的CPU密集度較低。

Answer 4

你基本上是在編寫一個迭代版本，但是使用尾遞歸進行循環。而且，通過使這麼多的變量成爲靜態的，你基本上使用全局變量而不是對象。這是一個更接近典型遞歸實現的嘗試。當然，在現實生活中，如果您使用的Java語言不優化尾部呼叫，您可以使用循環實現「Max」函數。

public class RecursiveTry{ 
    static int[] n; 

    public static void main(String[] args){ 
     RecursiveTry t = new RecursiveTry(new int[] {1,2,4,3,3,32,100}); 
     System.out.println(t.Max()); 
    }  

    RecursiveTry(int[] arg) { 
    n = arg; 
    } 

    public int Max() { 
    return MaxHelper(0); 
    } 

    private int MaxHelper(int index) { 
    if(index == n.length-1) { 
     return n[index]; 
    } else { 
     int maxrest = MaxHelper(index+1); 
     int current = n[index]; 
     if(current > maxrest) 
     return current; 
     else 
     return maxrest; 
    } 
    } 
} 

Answer 5

「不是家庭作業」？

無論如何。首先要做的事情。

static int[] n = new int[] {1,2,4,3,3,32,100}; 
static int SIZE = n.length; 

與他們共享其名稱的Max（）的參數無關。將這些移到main並丟失「靜態」說明符。當從main（）中調用Max（）的第一個實例時，它們僅用於一次。它們的範圍不應超出main（）。

沒有理由讓所有的M​​ax（）調用共享一個「當前」索引。 「當前」應該是Max（）的本地。但是，如何連續重複Max（）知道使用什麼值的「current」？ （提示：Max（）已經通過其他Max（）向下的一些數據，向這個數據添加「current」。）

maxValue也是一樣，儘管這裏的情況有點多複雜。您不僅需要傳遞當前的「maxValue」，而且遞歸完成後，必須將其傳遞迴第一個Max（）函數，該函數將返回到main（）。你可能需要看一些遞歸的例子，並花一些時間用這個例子。

最後，Max（）本身是靜態的。一旦你消除了引用外部數據（靜態變量）的需要，它並不重要。它只是意味着你可以調用Max（）而不必實例化一個對象。

Answer 6

使你的函數依賴於靜態變量不是一個好主意。這是可能實現的遞歸最大的功能：

int Max(int[] array, int currentPos, int maxValue) { 
    // Ouch! 
    if (currentPos < 0) { 
     raise some error 
    } 
    // We reached the end of the array, return latest maxValue 
    if (currentPos >= array.length) { 
     return maxValue; 
    } 
    // Is current value greater then latest maxValue ? 
    int currentValue = array[currentPos]; 
    if (currentValue > maxValue) { 
     // currentValue is a new maxValue 
     return Max(array, currentPos + 1, currentValue); 
    } else { 
     // maxValue is still a max value 
     return Max(array, currentPos + 1, maxValue); 
    } 
} 
... 

int[] array = new int[] {...}; 
int currentPos = 0; 
int maxValue = array[currentPos] or minimum int value; 
    maxValue = Max(array, currentPos, maxValue); 

Answer 7

正如其他人所觀察到的，沒有需要遞歸來實現最大的功能，但它可以啓發使用熟悉算法與新的嘗試概念。所以，這裏是簡化的代碼，下面的解釋如下：

public class RecursiveTry 
{ 
    public static void main(String[] args) 
    { 
     System.out.println(Max(new int[] {1,2,4,3,3,32,100}, 0, 0)); 
    } 

    public static int Max(int[] n, int current, int maxValue) 
    { 
     if(current < n.Length) 
     { 
      if (maxValue <= n[current] || current == 0)) 
      { 
       return Max(n, current+1, n[current]); 
      } 
      return Max(n, current+1, maxValue); 
     } 
     return maxValue; 
    } 
} 

所有的靜態狀態都是不必要的;相反，所有東西都在堆棧上傳遞。 Max函數的內部邏輯被精簡，我們以兩種不同的方式遞歸，僅僅爲了樂趣

Answer 8

你的確在過度使用靜態。你也不需要太多的全局變量。嘗試移動

static int [] n = new int [] {1,2,4,3,3,32,100}; static int current = 0; static int maxValue = 0; static int SIZE = n.length;

到您的main（）函數中，以便它們是局部變量。

public static void main(String[] args) 
{ 
    int[] n = new int[] {1,2,4,3,3,32,100}; 
    int current = 0; 
    int maxValue = 0; 
    int SIZE = n.length; 
    ...other code 

} 

不解決您的主要問題，而是利用對全球那些局部變量（一般）

其良好的做法---當我做完這個，我意識到，我只是動什麼AIB以上

Answer 9

說，在這個方案可以非常簡潔地寫：

(define (max l) 
    (if (= (length l) 1) 
     (first l) 
     (local ([define maxRest (max (rest l))]) 
      (if (> (first l) maxRest) 
       (first l) 
       maxRest)))) 

當然，這使用鏈表，而不是數組，這就是爲什麼我沒有通過它的尺寸ELE但我覺得這個問題的本質就是問題。這是僞代碼定義：

define max of a list as: 
    if the list has one element, return that element 
    otherwise, the max of the list will be the max between the first element and the max of the rest of the list 

Answer 10

這是您的Java版本。

public class Recursion { 

    public static void main(String[] args) { 
     int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 
     System.out.println("Max: " + max(0, data)); 
    } 

    public static int max(int i, int[] arr) { 
     if(i == arr.length-1) { 
      return arr[i]; 
     } 

     int memo = max(i+1, arr); 
     if(arr[i] > memo) { 
      return arr[i]; 
     } 
     return memo; 
    } 
} 

的遞推關係是一個數組的最大元素是第一元素，或最大的陣列的其餘部分的。到達陣列末尾時達到停止條件。請注意使用memoization將遞歸調用（大致）減半。

Answer 11

遞歸獲取數組最大值的更好方法是實現quicksort（這是一個很好的遞歸排序算法），然後返回第一個值。

這裏是一些Java code for quicksort。

Answer 12

最小codesize我可以得到：

public class RecursiveTry { 
    public static void main(String[] args) { 
     int[] x = new int[] {1,2,4,3,3,32,100}; 
     System.out.println(Max(x, 0)); 
    } 

    public static int Max(int[] arr, int currPos) { 
     if (arr.length == 0) return -1; 
     if (currPos == arr.length) return arr[0]; 
     int len = Max (arr, currPos + 1); 
     if (len < arr[currPos]) return arr[currPos]; 
     return len; 
    } 
} 

有幾件事情：

1 /如果數組是零大小，則返回-1最大（你可以有另一種標記值，比如說，-MAX_INT，或拋出異常）。我在此假設代碼清晰，假設所有值都爲零或更多。否則，我會用各種不必要的東西（關於回答這個問題）給代碼加註。

2 /在我看來，如果終止的情況是無數據而不是最後數據，那麼大多數遞歸都是'更清晰'的，因此我返回的值保證小於或等於最大值陣列。其他人可能會有不同意見，但這不會是他們第一次或最後一次錯誤:-)。

3 /遞歸調用只是獲取列表中其餘部分的最大值，並將其與當前元素進行比較，返回兩者中的最大值。

4理想的解決方案應該是在每次遞歸調用時傳遞一個修改過的數組，以便您只將第一個元素與列表的其餘部分進行比較，從而不再需要currPos。但那樣會效率低下，並會降低SO的憤怒。

5 /這可能不一定是最好的解決方案。這可能是灰色物質由於其CAR，CDR和那些無窮無盡的括號過度使用LISP而受到損害。