java - 递归 - 试图理解

Question

我有下一个方法:

public static int maxFind(int [] a, int length)
{
  if (length == 1){
          return a[0];
  }

  // recursively maxFind method on length-1
  int result = maxFind(a, length - 1);

  if (a[length - 1] > result)
    return a[length - 1];
  else
    return result;

}

我已经完成了这项工作，并且在我看到该方法的教程后过了一段时间，我总是忘记递归的想法。我认为如果有人能向我解释这个方法的每一步 - 我就会一劳永逸地明白这个想法。

示例 - 我的arr 是:{1,1,0,2)

当我们运行这个方法时，这里的步骤是什么？ result 的值是什么， (a, length-1) 的作用是什么？ (我已经尝试过调试器，但它对我没有帮助)

Answer 1

让我看看是否可以阐明这个主题。

在考虑递归时，以更具声明性的方式思考程序会有所帮助(至少对我来说)，这意味着，您会考虑要实现的目标，而不是考虑所需算法的每一步来完成它。

让我们检查一下您的示例，您需要找到数组中的最大值，因此我们将把这个问题分解为更小的问题。

如果数组的大小为 1，则只有一个元素...因此 1 是最大元素。简单。

求最大值的问题可以描述为:列表中的一个元素与所有其他元素中的最大值之间的较大值。

这就是您在其余代码中所做的事情。您将算法应用于从位置 0 到 length-1 的数组，然后比较返回值。

这些调用将创建一个递归树，这意味着，将有多个“嵌套”调用，直到每个调用都以 length=1(基本情况)完成，然后然后，算法将开始重建答案。

真正理解递归算法的最好方法是抓一张纸并模拟程序，每次调用时在纸上写下数组的值和“长度”的值，然后弄清楚会发生什么每次调用最终达到基本情况后。

对于 {1,1,0,2}，您基本上会收到一系列调用，例如:

max(maxFind({1,1,0}), 2)

其中 maxFind({1,1,0}) 归结为:

max(maxFind({1,1}), 0)

maxFind({1,1}) 为

max(1,1)  = 1

然后这开始沸腾(与上面的顺序相反):

max(1, 0) = 0
max(1, 2) = 2 

所以结果将是2。