在scala中以递归方式查找列表中的最大值

Question

我是Scala的新手,有更好的方法可以用最基本的知识表达这一点吗？

 def findMax(xs: List[Int]): Int = {
      xs match {
        case x :: tail => (if (tail.length==0) x else (if(x>findMax(tail)) x else (findMax(tail))))
      }
    }

Answer 1

你在这里有两个问题.首先,您调用tail.length哪个是顺序操作O(N),因此在最坏的情况下,这将花费您N*N步骤,其中N是序列的长度.第二个是你的函数不是尾递归 - 你将findMax调用嵌套在"从外到内".

编写正确的递归函数的通常策略是

• 考虑每种可能的模式案例:这里有空列表Nil或非空列表head :: tail.这解决了您的第一个问题.
• 携带临时结果(这里是最大值的当前猜测)作为函数的另一个参数.这解决了你的第二个问题.

这给出了:

import scala.annotation.tailrec

@tailrec
def findMax(xs: List[Int], max: Int): Int = xs match {
  case head :: tail => findMax(tail, if (head > max) head else max)
  case Nil => max
}

val z = util.Random.shuffle(1 to 100 toList)
assert(findMax(z, Int.MinValue) == 100)

如果您不想公开此附加参数,则可以编写辅助内部函数.

def findMax(xs: List[Int]): Int = {
  @tailrec
  def loop(ys: List[Int], max: Int): Int = ys match {
    case head :: tail => loop(tail, if (head > max) head else max)
    case Nil => max
  }
  loop(xs, Int.MinValue)
}

val z = util.Random.shuffle(1 to 100 toList)
assert(findMax(z) == 100)

为简单起见,Int.MinValue如果列表为空,则返回.更好的解决方案可能是为此案例抛出异常.

@tailrec这里的注释是可选的,它只是确保我们确实定义了一个尾递归函数.这样做的好处是,如果列表非常长,我们就不会产生堆栈溢出.

Answer 2

每次将集合缩减为单个值时,请考虑使用折叠函数之一而不是显式递归.

List(3,7,1).fold(Int.MinValue)(Math.max)
// 7