递归 - 试图了解

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; 

} 

我已经完成了这项工作，并从当我看到那个方法的教程经过一段时间，我总是忘了递归的想法。我认为如果有人会向我解释这一方法的每一步 - 我会一劳永逸地提出这个想法。

例子 - 我的改编是：{1,1,0,2）

什么是这里的步骤，当我们运行这个方法？结果的价值是什么，（a，长度为1）的作用是什么？ （我试过调试器，但它没有帮助我）

Answer 1

我会试着一步一步解释：

首先调用与参数{1,1,0,2}和4个方法

1）max_find（[1,1,0,2]，4）=>长度不是1，以便max_find将再次与长度被称为= 4-1

2）max_find（[1,1 ，0,2]，3）=>长度不是1，所以max_find将再次被调用，长度= 3-1

3）max_find（[1,1,0,2]，2）=>长度不是1，以便max_find将再次与长度被称为= 2-1

4）max_find（[1,1 ，0,2]，1）=>长度为1，所以将返回一个[0]，即1

5）现在代码形式步骤3评估步骤4的结果=> a [2-1 ]不是> 1，所以它返回1

6）现在的代码形式的步骤2从步骤评估结果3 =>一个[3-1]不> 1，所以它返回1

7 ）现在代码表单步骤1评估结果fr OM步骤2 =>一个[4-1]> 1，所以它返回一个[4-1]，这是2

完成

Answer 2

这个想法基本上是你做了完全相同的东西，只是输入数据的一点点改变。

代码本身很简单：

• 第一if检查递归结束
• 的int result线做递归
• 你lookes的最大元素，并返回它的结束。

Answer 3

让我看看我是否可以在这个问题上提出一些看法。

在考虑递归时，它有助于（至少是我）以更具说明性的方式思考程序，也就是说，考虑您要完成的内容，而不是考虑算法的每一步需要完成它。

让我们来看看你的例子，你需要在一个数组中找到最大值，所以我们将在较小的问题中分解这个问题。

如果数组的大小为1，那么只有一个元素...所以一个是最大的。简单。

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

这就是你在做的其他代码。您将算法应用于数组，从位置0到长度1，然后比较返回值。

这些电话将创建一个递归树，意义，会有多个呼叫“嵌套”，直到每个呼叫与长度= 1（基础情况）完成，并且然后，算法将开始重建的答案。

真正理解递归算法的最好方法是抓住一张纸并模拟程序，在纸上为每次调用写入数组的值和“length”的值，然后弄清楚在每次通话最终达到基本情况后发生。

对于{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

Answer 4

什么是对结果的值

那么这就是递归点：没有一个值结果，这可能是什么让你感到困惑。结果的值依次为1,1,1,1,2。

当我们运行此方法时，这里的步骤是什么？

这里发生的事情：用递归方法工作时

What is the max of: {1} ? Result is: 1 
What is the max of: {(1), 1} ? Result is: 1 
What is the max of: {(1, 1), 0} ? Result is: 1 
What is the max of: {(1, 1, 0), 2} ? Result is: 2 

注意调试的确不是小事。它有时帮助更多的打印方法调用“缩进”的深度递归级别，像这个问题我回答在这里：

How do I solve the 'classic' knapsack algorithm recursively?

（你需要以某种方式保持“深度跟踪的过程'递归调用）

和（a，长度-1）的作用是什么？ （我已经尝试了调试，但 它没有帮助我）

调试器可能不会因为为了节省内存在Java中的方法是使用一个“窍门”帮助您：基本输入被缩短表明你不应该分析整个数组。但是你仍然递归地将整个数组传递给方法。这是一个“穷人获得少一个元素的清单的功能性方式”; ）

下面是一个链接，显示如何找到不同语言的lot中的列表的最大值。他们中的一些，像OCaml的一个，表示以函数形式：OCaml中的

http://rosettacode.org/wiki/Greatest_element_of_a_list

三线（来源：维基百科）：

let my_max = function 
    [] -> invalid_arg "empty list" 
    | x::xs -> List.fold_left max x xs