2

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

  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
  }

打印出来的语句告诉我，我已经成功地将 List 中的最大值作为头部（这是我想要的），但该函数仍然返回列表中的原始头部。我猜这是因为 xs 的引用仍然是指原始 xs 列表，问题是我不能覆盖它，因为它是一个 val。

任何想法我做错了什么？

4

8 回答 8

3

您应该使用对 max 的内部调用的返回值并将其与本地最大值进行比较。类似于以下内容（删除 println 只是为了便于阅读）：

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

再见。

于 2013-09-17T21:41:36.707 回答
2

我有你的问题的答案，但首先...

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

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 )
}

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

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

max(remaining)

至

largest = max(remaining)

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

解决此问题的另一种方法是在声明var largest. 那看起来像这样：

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
  }

不过，一般来说，最好让递归函数完全自包含（即，不查看或更改外部变量，而只查看它们的输入）并返回一个有意义的值。

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

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

如果您查看我的解决方案，您会发现第一个case处理无效输入，第二个是我的退出条件，第三个是“如果我们不在最后该怎么办”。

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

这就是我（一如既往）推荐阅读The Little Schemer 的地方。它同时教您递归（和基本方案）（两者都是非常好的学习内容）。

有人指出，Scala 有一些强大的功能可以帮助您避免递归（或隐藏它的混乱细节），但要很好地使用它们，您确实需要了解递归的工作原理。

于 2013-09-18T07:31:05.030 回答
2

以下是解决此类问题的典型方法。它使用一个内部尾递归函数，其中包含一个额外的“累加器”值，在这种情况下，它将保存迄今为止发现的最大值：

def max(xs: List[Int]): Int = {
  def go(xs: List[Int], acc: Int): Int = xs match {
    case Nil => acc // We've emptied the list, so just return the final result
    case x :: rest => if (acc > x) go(rest, acc) else go(rest, x) // Keep going, with remaining list and updated largest-value-so-far
  }

  go(xs, Int.MinValue)
}
于 2013-09-17T21:47:57.563 回答
0

我见过的最简洁但也最清晰的版本是这样的：

def max(xs: List[Int]): Int = {
    def maxIter(a: Int, xs: List[Int]): Int = {
        if (xs.isEmpty) a
        else a max maxIter(xs.head, xs.tail)
    }
    maxIter(xs.head, xs.tail)
}

这已从解决方案改编为 Scala 官方 Corusera 课程的家庭作业：https ://github.com/purlin/Coursera-Scala/blob/master/src/example/Lists.scala

但在这里我使用丰富的运算符max来返回它的两个操作数中最大的一个。这样就不必在def max块中重新定义此函数。

于 2013-12-13T06:49:06.080 回答
0

那这个呢？

def max(xs: List[Int]): Int = {
    maxRecursive(xs, 0)
  }

  def maxRecursive(xs: List[Int], max: Int): Int = {
    if(xs.head > max && ! xs.isEmpty)
       maxRecursive(xs.tail, xs.head)
    else
      max

  }
于 2014-04-26T10:53:22.637 回答
0

这个如何 ？

 def max(xs: List[Int]): Int = {
    var largest = xs.head
    if( !xs.tail.isEmpty ) {
      if(xs.head < max(xs.tail)) largest = max(xs.tail)     
    }  
    largest
  }
于 2014-07-08T06:38:43.643 回答
0

没关系，我已经解决了这个问题......

我终于想出了：

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

有点高兴我们有循环 - 这是一个过于复杂的解决方案，在我看来很难理解。我通过确保递归调用是函数中的最后一条语句来解决问题，或者如果数组中没有第二个成员，则返回 xs.head 作为结果。

于 2013-09-17T21:40:32.820 回答
0

我的答案是使用递归是，

def max(xs: List[Int]): Int =
  xs match {
    case Nil => throw new NoSuchElementException("empty list is not allowed")
    case head :: Nil => head
    case head :: tail =>
      if (head >= tail.head)
        if (tail.length > 1)
            max(head :: tail.tail)
        else
          head
      else
        max(tail)
  }
}
于 2016-09-15T13:58:17.787 回答