在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

无论何时您将某个集合减少为单个值，都应考虑使用fold函数之一而不是显式递归。

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

Answer 3

使用模式匹配的递归，

def top(xs: List[Int]): Int = xs match { 
    case Nil  => sys.error("no max in empty list") 
    case x :: Nil => x 
    case x :: xs => math.max(x, top(xs)) 
} 

模式匹配用于分解列表分成头和休息。单个元素列表用x :: Nil表示。我们在列表的其余部分进行递归，并在每个递归阶段比较列表头项上的最大值。为了使案例穷举（做一个明确定义的函数），我们也考虑空列表（Nil）。

Answer 4

def maxl(xl: List[Int]): Int = { 
    if ((xl.head > xl.tail.head) && (xl.tail.length >= 1)) 
    return xl.head 
    else 
    if(xl.tail.length == 1) 
     xl.tail.head 
    else 
     maxl(xl.tail) 
}