为什么我的递归函数不返回列表的最大值 [英] Why doesn't my recursive function return the max value of a List

问题描述

我在 Scala 中有以下递归函数，它应该返回列表中的最大大小整数.谁能告诉我为什么不返回最大值?

I have the following recursive function in Scala that should return the maximum size integer in the List. Is anyone able to tell me why the largest value is not returned?

  def max(xs: List[Int]): Int = {
    var largest = xs.head
    println("largest: " + largest)
    if (!xs.tail.isEmpty) {
      var next = xs.tail.head
      println("next: " + next)
      largest = if (largest > next) largest else next
      var remaining = List[Int]()
      remaining = largest :: xs.tail.tail
      println("remaining: " + remaining)
      max(remaining)
    }
    return largest
  }

打印输出语句告诉我，我已经成功地将列表中的最大值带回作为头部(这是我想要的)，但该函数仍然返回列表中的原始头部.我猜这是因为 xs 的引用仍然是指原始的 xs 列表，问题是我无法覆盖它，因为它是一个 val.

Print out statements show me that I've successfully managed to bring back the largest value in the List as the head (which was what I wanted) but the function still returns back the original head in the list. I'm guessing this is because the reference for xs is still referring to the original xs list, problem is I can't override that because it's a val.

知道我做错了什么吗?

推荐答案

我已经回答了你的问题，但首先...

I have an answer to your question but first...

这是我能想到的最小的 max 递归实现:

This is the most minimal recursive implementation of max I've ever been able to think up:

def max(xs: List[Int]): Option[Int] = xs match {
  case Nil => None
  case List(x: Int) => Some(x)
  case x :: y :: rest => max( (if (x > y) x else y) :: rest )
} 

(好吧，我的原始版本稍微小了一点，但我在没有 Option 或类型安全等的 Scheme 中写了它.)它不需要累加器或本地帮助函数，因为它比较第一个列表中的两个项目并丢弃较小的项目，这个过程 - 递归执行 - 不可避免地给您留下一个只有一个元素的列表，该列表必须比所有其他元素都大.

(OK, my original version was ever so slightly more minimal but I wrote that in Scheme which doesn't have Option or type safety etc.) It doesn't need an accumulator or a local helper function because it compares the first two items on the list and discards the smaller, a process which - performed recursively - inevitably leaves you with a list of just one element which must be bigger than all the rest.

好的，为什么您的原始解决方案不起作用...很简单:您对 max 的递归调用的返回值不做任何处理.所有你所要做的就是改变线路

OK, why your original solution doesn't work... It's quite simple: you do nothing with the return value from the recursive call to max. All you had to do was change the line

max(remaining)

到

largest = max(remaining)

并且您的功能会起作用.这不会是最漂亮的解决方案，但它会起作用.实际上，您的代码看起来好像假设在递归调用中更改 largest 的值将在调用它的外部上下文中更改它.但是每次对 max 的新调用都会创建一个全新的 largest 版本，它只存在于函数的新迭代中.然后，您的代码丢弃 max(remaining) 的返回值，并返回未更改的 largest 的原始值.

and your function would work. It wouldn't be the prettiest solution, but it would work. As it is, your code looks as if it assumes that changing the value of largest inside the recursive call will change it in the outside context from which it was called. But each new call to max creates a completely new version of largest which only exists inside that new iteration of the function. Your code then throws away the return value from max(remaining) and returns the original value of largest, which hasn't changed.

解决此问题的另一种方法是在声明var最大之后使用本地(内部)函数.应该是这样的:

Another way to solve this would have been to use a local (inner) function after declaring var largest. That would have looked like this:

def max(xs: List[Int]): Int = {
    var largest = xs.head
    def loop(ys: List[Int]) {
      if (!ys.isEmpty) {
        var next = ys.head
        largest = if (largest > next) largest else next
        loop(ys.tail)
      }
    }
    loop(xs.tail)
    return largest
  } 

不过，一般而言，最好让递归函数完全独立(即，不查看或更改外部变量，而只查看其输入)并返回有意义的值.

Generally, though, it is better to have recursive functions be entirely self-contained (that is, not to look at or change external variables but only at their input) and to return a meaningful value.

在编写此类递归解决方案时，逆向思考通常会有所帮助.首先想想当你到达列表的末尾时，事情会是什么样子.退出条件是什么?事情会是什么样子，我在哪里可以找到要返回的值?

When writing a recursive solution of this kind, it often helps to think in reverse. Think first about what things are going to look like when you get to the end of the list. What is the exit condition? What will things look like and where will I find the value to return?

如果你这样做，那么你用来退出递归函数的case(通过返回一个简单的值而不是进行另一个递归调用)通常非常简单.其他 case 匹配只需要处理 a) 无效输入和 b) 如果您还没有到最后该怎么办.a) 通常很简单，而 b) 通常可以分解为几种不同的情况，在进行另一个递归调用之前，每种情况都有一个简单的事情要做.

If you do this, then the case which you use to exit the recursive function (by returning a simple value rather than making another recursive call) is usually very simple. The other case matches just need to deal with a) invalid input and b) what to do if you are not yet at the end. a) is usually simple and b) can usually be broken down into just a few different situations, each with a simple thing to do before making another recursive call.

如果您查看我的解决方案，您会看到第一个 case 处理无效输入，第二个是我的退出条件，第三个是如果我们不在时该怎么办"结束".

If you look at my solution, you'll see that the first case deals with invalid input, the second is my exit condition and the third is "what to do if we're not at the end".

在许多其他递归解决方案中，Nil 是递归的自然结束.

In many other recursive solutions, Nil is the natural end of the recursion.

这是我(一如既往)推荐阅读The Little Schemer.它同时教你递归(和基本的 Scheme)(这两个都是非常好的学习).

This is the point at which I (as always) recommend reading The Little Schemer. It teaches you recursion (and basic Scheme) at the same time (both of which are very good things to learn).

有人指出 Scala 有一些强大的函数可以帮助您避免递归(或隐藏其混乱的细节)，但是要很好地使用它们，您确实需要了解递归的工作原理.

It has been pointed out that Scala has some powerful functions which can help you avoid recursion (or hide the messy details of it), but to use them well you really do need to understand how recursion works.

这篇关于为什么我的递归函数不返回列表的最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！