递归查找链表的最大值

Question

我需要在一个名为 Node 的类中编写一个名为 findMax 的 Java 方法，该方法有两个实例变量：int value 和 Node next。该方法不带任何参数，并且必须返回链表的最大值。在程序的上下文中，该方法将始终由链表的第一个节点调用(递归调用除外)。当我意外找到一个可行的解决方案时，我正在努力完成该方法：

public int findMax(){
int max = value;
if(next == null){
return max;
}
else{
if(max <= next.findMax()){
max = next.value;
}
else return max;
}
return next.findMax();
}

此方法正确返回了我测试的每个链表的最大值。但是，由于我通过尝试随机排列代码找到了这个解决方案，所以我真的不觉得我明白这里发生了什么。谁能向我解释一下这是如何/为什么工作的？此外，如果有更有效的解决方案，它将如何实施？

Answer 1

你可以想象一个链表看起来像这样：

val1 -> val2 -> val3 -> null

递归的工作原理是，最终，您传递给函数的输入可以在不进一步递归的情况下进行处理。在您的情况下，如果next指针null，则可以处理 node.findMax()。也就是说，大小为 1 的链表的最大值只是值(递归的基本情况)，任何其他链表的最大值是该节点值的最大值或其余元素的最大值。

ie) 对于值为 val3 的Node n3，n3.findMax()只返回值

对于任何其他节点n，n.findMax()返回节点值的最大值或n.next.findMax()

在开始时的示例中，它的外观是：

n1.findMax()
= Max(n1.value, n2.findMax())
= Max(val1, Max(n2.value, n3.findMax())
= Max(val1, Max(val2, n3.value)) // Since n3.next == null
= Max(val1, Max(val2, val3))

这只是整个列表中的最大值

编辑：基于上面的讨论，虽然你说的可能有效，但有一种更简单的程序编写方法：

int findMax() {
if (this.next == null) {
return this.value;
} else {
return Math.max(this.value, this.next.findMax());
}
}

编辑2：分解为什么你的代码工作(以及为什么它不好)：

public int findMax(){
// This variable doesn't serve much purpose
int max = value;
if(next == null){
return max;
}
else{
// This if condition simply prevents us from following
// the else block below but the stuff inside does nothing.
if(max <= next.findMax()){
// max is never used again if you are here.
max = next.value;
}
else return max;
}
// We now compute findMax() again, leading to serious inefficiency
return next.findMax();
}

为什么效率低下？因为对节点上的findMax()的每个调用都会对下一个节点上的findMax()进行两次后续调用。这些调用中的每一个都将生成另外两个调用，依此类推。

解决此问题的方法是存储next.findMax()的结果，如下所示：

public int findMax() {
if (next == null) {
return value;
}
else {
int maxOfRest = next.findMax();
if(value <= maxOfRest) {
return maxOfRest;
}
else return value;
}
}