使用遞歸

Question

我是一個算法beginner.I剛剛制定了一個解決方案，「遞歸找到整型數組的最大元素」查找數組中的最大元素：

public static int findMax(int[]arr) 
{ 

    if(arr.length==1) 
    return arr[0]; 

    return findMax(Arrays.copyOf(arr, arr.length-1))> arr[arr.length-1]?findMax(Arrays.copyOf(arr, arr.length-1)):arr[arr.length-1]; 
} 

我做了多次測試，它似乎正常工作。

然而，我發現有人使用其他的遞歸方法解決了這個問題太喜歡在這個崗位：

finding max value in an array using recursion java

他的代碼如下：

int largest(int[] a, int start, int largest) 
{ 
    if (start == a.length) 
    return largest; 
    else { 
    int l = (a[start] > largest ? a[start] : largest); 
    return largest(a, start + 1, l); 
} 

我在這裏停留在本質在我們的思維方式上存在這個問題的差異。我的想法如下：

1.he使用另一個參數「start」來保持trac當前遊標的k在每次遞歸中都是數組元素，我沒有使用它，因爲我在每次遞歸中將數組縮小1，並始終使用尾部元素進行比較;

2.he使用另一個參數「最大」來跟蹤到目前爲止發現的最大值。我沒有在我的代碼中使用這個，但我沒有使用它。而這實際上就是我卡住的地方。我沒有使用那個「最大的」變量來跟蹤每次迭代中的最大值，爲什麼我可以達到相同的結果？

任何幫助，非常感謝！

Answer 1

首先，n.m說的是正確的，複製數組是昂貴的和不必要的。另一個算法使用start來避免這種情況。

但你的問題。你實際上使用最大的只是沒有任何名稱！

return findMax(Arrays.copyOf(arr, arr.length-1))> arr[arr.length-1]?findMax(Arrays.copyOf(arr, arr.length-1)):arr[arr.length-1]; 

是您發現最大的地方。它就像你提到的另一種算法。首先你找到最大的：findMax(Arrays.copyOf(arr, arr.length-1))，然後你將它的值與：arr[arr.length-1]比較，選擇大一點的是你目前最大的。

另一個建議，爲什麼你需要撥打findMax(Arrays.copyOf(arr, arr.length-1))兩次？只需使用一個變量來提高算法速度。