使用递归

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))两次？只需使用一个变量来提高算法速度。