list 如何递归地找到整数列表中的最大元素？

How to find the largest element in a list of integers recursively?

提问by nazar_art

I'm trying to write a function which will recursively find the largest element in a list of integers. I know how to do this in Java, but can't understand how to do this at Scala.

我正在尝试编写一个函数，该函数将递归地查找整数列表中的最大元素。我知道如何在 Java 中执行此操作，但无法理解如何在 Scala 中执行此操作。

Here is what I have so far, but without recursion:

这是我到目前为止所拥有的，但没有递归：

  def max(xs: List[Int]): Int = {
    if (xs.isEmpty) throw new java.util.NoSuchElementException();
    else xs.max;
  }

How can we find it recursively with Scala semantic.

我们如何使用 Scala 语义递归地找到它。

回答by itsbruce

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

这是我能想到的最小的 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 )
} 

It works by comparing the first two elements on the list, discarding the smaller (or the first, if both are equal) and then calling itself on the remaining list. Eventually, this will reduce the list to one element which must be the largest.

它的工作原理是比较列表中的前两个元素，丢弃较小的（或第一个，如果两者相等），然后在剩余的列表上调用自身。最终，这会将列表减少到一个必须是最大的元素。

I return an Option to deal with the case of being given an empty list without throwing an exception - which forces the calling code to recognise the possibility and deal with it (up to the caller if theywant to throw an exception).

我返回一个 Option 来处理在不抛出异常的情况下给出一个空列表的情况 - 这迫使调用代码识别可能性并处理它（如果他们想抛出异常，则由调用者决定）。

If you want it to be more generic, it should be written like this:

如果你想让它更通用，它应该这样写：

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

Which will work with any type which either extends the Orderedtrait or for which there is an implicit conversion from Ato Ordered[A]in scope. So by default it works for Int, BigInt, Char, Stringand so on, because scala.Predef defines conversions for them.

这将与任一延伸的任何类型的工作Ordered特性或针对其存在由隐式转换A到Ordered[A]在范围内。因此，在默认情况下它的工作原理为Int，BigInt，Char，String等等，因为scala.Predef定义为他们的转换。

We can become yet more generic like this:

我们可以像这样变得更通用：

def max[A <% Ordered[A]](xs: Seq[A]): Option[A] = xs match {
  case s if s.isEmpty || !s.hasDefiniteSize => None
  case s if s.size == 1 => Some(s(0))
  case s if s(0) <= s(1) => max(s drop 1)
  case s => max((s drop 1).updated(0, s(0)))
}

Which will work not just with lists but vectors and any other collection which extends the Seqtrait. Note that I had to add a check to see if the sequence actually has a definite size - it might be an infinite stream, so we back away if that might be the case. If you are sure your stream will have a definite size, you can always force it before calling this function - it's going to work through the whole stream anyway. See notes at the end for why I reallywould not want to return Nonefor an indefinite stream, though. I'm doing it here purely for simplicity.

这不仅适用于列表，还适用于向量和任何其他扩展Seqtrait 的集合。请注意，我必须添加一个检查以查看序列是否确实具有确定的大小 - 它可能是一个无限流，因此如果可能是这种情况，我们将退出。如果你确定你的流有一个确定的大小，你可以在调用这个函数之前强制它 - 无论如何它都会在整个流中工作。不过，请参阅最后的注释，了解为什么我真的不想返回None无限期的流。我在这里这样做纯粹是为了简单。

But this doesn't work for sets and maps. What to do? The next common supertype is Iterable, but that doesn't support updatedor anything equivalent. Anything we construct might be very poorly performing for the actual type. So my clean no-helper-function recursion breaks down. We couldchange to using a helper function but there are plenty of examples in the other answers and I'm going to stick with a one-simple-function approach. So at this point, we can to switch to reduceLeft(and while we are at it, let's go for `Traversable' and cater for allcollections):

但这不适用于集合和地图。该怎么办？下一个常见的超类型是Iterable，但它不支持updated或任何等效的东西。我们构造的任何东西对于实际类型的性能都可能很差。所以我干净的无辅助函数递归崩溃了。我们可以改为使用辅助函数，但其​​他答案中有很多示例，我将坚持使用单一函数的方法。所以在这一点上，我们可以切换到reduceLeft（当我们在做的时候，让我们选择 `Traversable' 并满足所有集合）：

def max[A <% Ordered[A]](xs: Traversable[A]): Option[A] = {
  if (xs.hasDefiniteSize) 
    xs reduceLeftOption({(b, a) => if (a >= b) a else b}) 
  else None
}

but if you don't consider reduceLeft recursive, we can do this:

但如果你不考虑 reduceLeft 递归，我们可以这样做：

def max[A <% Ordered[A]](xs: Traversable[A]): Option[A] = xs match {
  case i if i.isEmpty => None
  case i if i.size == 1 => Some(i.head)
  case i if (i collect { case x if x > i.head => x }).isEmpty => Some(i.head)
  case _ => max(xs collect { case x if x > xs.head => x })
}

It uses the collectcombinator to avoid some clumsy method of bodging a new Iterator out of xs.headand xs drop 2.

它使用collect组合器来避免一些笨拙的方法，将新的迭代器从xs.head和 中取出xs drop 2。

Either of these will work safely with almost any collection of anything which has an order. Examples:

这些中的任何一个都可以安全地处理几乎所有有订单的任何集合。例子：

scala>  max(Map(1 -> "two", 3 -> "Nine", 8 -> "carrot"))
res1: Option[(Int, String)] = Some((8,carrot))

scala> max("Supercalifragilisticexpialidocious")
res2: Option[Char] = Some(x)

I don't usually give these others as examples, because it requires more expert knowledge of Scala.

我通常不会将这些其他人作为示例，因为它需要更多的 Scala 专业知识。

Also, do remember that the basic Traversabletrait provides a maxmethod, so this is all just for practice ;)

另外，请记住基本Traversable特征提供了一种max方法，所以这只是为了练习;)

Note: I hope that all my examples show how careful choice of the sequence of your case expressions can make each individual case expression as simple as possible.

注意：我希望我的所有示例都表明，仔细选择 case 表达式的顺序可以使每个单独的 case 表达式尽可能简单。

More Important Note:Oh, also, while I am intensely comfortable returning Nonefor an input of Nil, in practice I'd be strongly inclined to throw an exception for hasDefiniteSize == false. Firstly, a finite stream could have a definite or non-definite size dependent purely on the sequence of evaluation and this function would effectively randomly return Optionin those cases - which could take a long time to track down. Secondly, I would want people to be able to differentiate between having passed Niland having passed truly risk input (that is, an infinite stream). I only returned Optionin these demonstrations to keep the code as simple as possible.

更重要的注意事项：哦，虽然我非常乐意返回None的输入Nil，但实际上我强烈倾向于为 抛出异常hasDefiniteSize == false。首先，有限流可能具有确定或不确定的大小，完全取决于评估序列，并且Option在这些情况下，该函数将有效地随机返回——这可能需要很长时间来追踪。其次，我希望人们能够区分已经通过Nil和已经通过真正的风险输入（即无限流）。我只是Option在这些演示中返回以保持代码尽可能简单。

回答by tiran

The easiest approach would be to use max function of TraversableOncetrait, as follows,

最简单的方法是使用TraversableOncetrait 的max 函数，如下所示，

val list = (1 to 10).toList
list.max

to guard against the emptiness you can do something like this,

为了防止空虚，你可以做这样的事情，

if(list.empty) None else Some(list.max)

Above will give you an Option[Int]

以上会给你一个 Option[Int]

My second approach would be using foldLeft

我的第二种方法是使用 foldLeft

(list foldLeft None)((o, i) => o.fold(Some(i))(j => Some(Math.max(i, j))))

or if you know a default value to be returned in case of empty list, this will become more simpler.

或者如果您知道在空列表的情况下要返回的默认值，这将变得更加简单。

val default = 0
(list foldLeft default)(Math.max)

Anyway since your requirement is to do it in recursive manner, I propose following,

无论如何，由于您的要求是以递归方式进行，我建议遵循，

def recur(list:List[Int], i:Option[Int] = None):Option[Int] = list match {
  case Nil => i
  case x :: xs => recur(xs, i.fold(Some(x))(j => Some(Math.max(j, x))))
}

or as default case,

或作为默认情况，

val default = 0
def recur(list:List[Int], i:Int = default):Int = list match {
  case Nil => i
  case x :: xs => recur(xs, i.fold(x)(j => Math.max(j, x)))
}

Note that, this is tail recursive. Therefore stack is also saved.

请注意，这是tail recursive. 因此堆栈也被保存。

回答by 4lex1v

If you want functional approach to this problem then use reduceLeft:

如果您想要解决此问题的功能方法，请使用reduceLeft：

def max(xs: List[Int]) = {
  if (xs.isEmpty) throw new NoSuchElementException
  xs.reduceLeft((x, y) => if (x > y) x else y)
}

This function specific for list of ints, if you need more general approach then use Orderingtypeclass:

此函数特定于整数列表，如果您需要更通用的方法，请使用Orderingtypeclass：

def max[A](xs: List[A])(implicit cmp: Ordering[A]): A = {
  if (xs.isEmpty) throw new NoSuchElementException
  xs.reduceLeft((x, y) => if (cmp.gteq(x, y)) x else y)
}   

reduceLeftis a higher-order function, which takes a function of type (A, A) => A, it this case it takes two ints, compares them and returns the bigger one.

reduceLeft是一个高阶函数，它接受一个类型为 的函数(A, A) => A，在这种情况下它接受两个整数，比较它们并返回较大的一个。

回答by Nam Vo

You could use pattern matching like that

你可以像那样使用模式匹配

def max(xs: List[Int]): Int = xs match {
  case Nil => throw new NoSuchElementException("The list is empty")
  case x :: Nil => x
  case x :: tail => x.max(max(tail)) //x.max is Integer's class method
}

回答by Tay Wee Wen

Scala is a functional language whereby one is encourage to think recursively. My solution as below. I recur it base on your given method.

Scala 是一种函数式语言，它鼓励人们递归地思考。我的解决方案如下。我根据你给定的方法重复它。

  def max(xs: List[Int]): Int = {
    if(xs.isEmpty == true) 0
    else{
      val maxVal= max(xs.tail)
      if(maxVal >= xs.head) maxVal 
      else                  xs.head     
    }
  }

Updated my solution to tail recursive thanks to suggestions.

由于建议，将我的解决方案更新为尾递归。

  def max(xs: List[Int]): Int = {    
    def _max(xs: List[Int], maxNum: Int): Int = {   
      if (xs.isEmpty) maxNum
      else {
        val max = {
          if (maxNum >= xs.head) maxNum
          else xs.head
        }
        _max(xs.tail, max)
      }
    }
    _max(xs.tail, xs.head)
  }

回答by Roman Kazanovskyi

I used just head() and tail ()

我只使用了 head() 和 tail ()

def max(xs: List[Int]): Int = {
    if (xs.isEmpty) throw new NoSuchElementException
    else maxRecursive(xs.tail,xs.head) 
  }

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

Here is test:

这里是测试：

test("max of a few numbers") {
    assert(max(List(3, 7, 2, 1, 10)) === 10)
    assert(max(List(3, -7, 2, -1, -10)) === 3)
    assert(max(List(-3, -7, -2, -5, -10)) === -2)
  }

回答by Arseniy Zhizhelev

1. Folding can help:

   if(xs.isEmpty)
     throw new NoSuchElementException
   else
     (Int.MinValue /: xs)((max, value) => math.max(max, value))
   

2. List and pattern matching (updated, thanks to @x3ro)

   def max(xs:List[Int], defaultValue: =>Int):Int = {
     @tailrec
     def max0(xs:List[Int], maxSoFar:Int):Int = xs match {
       case Nil => maxSoFar
       case head::tail => max0(tail, math.max(maxSoFar, head))
     }
     if(xs.isEmpty)
       defaultValue
     else
       max0(xs, Int.MinValue)
   }
   

1. 折叠可以帮助：

   if(xs.isEmpty)
     throw new NoSuchElementException
   else
     (Int.MinValue /: xs)((max, value) => math.max(max, value))
   

2. 列表和模式匹配（更新，感谢@x3ro）

   def max(xs:List[Int], defaultValue: =>Int):Int = {
     @tailrec
     def max0(xs:List[Int], maxSoFar:Int):Int = xs match {
       case Nil => maxSoFar
       case head::tail => max0(tail, math.max(maxSoFar, head))
     }
     if(xs.isEmpty)
       defaultValue
     else
       max0(xs, Int.MinValue)
   }
   

(This solution does not create Optioninstance every time. Also it is tail-recursive and will be as fast as an imperative solution.)

（此解决方案不会Option每次都创建实例。而且它是尾递归的，并且与命令式解决方案一样快。）

回答by Anand

Here is my code (I am a newbie in functional programming) and I'm assuming whoever lands up under this question will be folks like me. The top answer, while great, is bit too much for newbies to take! So, here is my simple answer. Note that I was asked (as part of a Course) to do this using only head and tail.

这是我的代码（我是函数式编程的新手），我假设遇到这个问题的人都会像我一样。最佳答案虽然很棒，但对于新手来说有点太多了！所以，这是我的简单回答。请注意，我被要求（作为课程的一部分）仅使用头部和尾部来执行此操作。

/**
   * This method returns the largest element in a list of integers. If the
   * list `xs` is empty it throws a `java.util.NoSuchElementException`.
   *
   * @param xs A list of natural numbers
   * @return The largest element in `xs`
   * @throws java.util.NoSuchElementException if `xs` is an empty list
   */
    @throws(classOf[java.util.NoSuchElementException])
    def max(xs: List[Int]): Int = find_max(xs.head, xs.tail)

    def find_max(max: Int, xs: List[Int]): Int = if (xs.isEmpty) max else if (max >= xs.head) find_max(max, xs.tail) else find_max(xs.head, xs.tail)

Some tests:

一些测试：

test("max of a few numbers") {
    assert(max(List(3, 7, 2)) === 7)
    intercept[NoSuchElementException] {
      max(List())
    }
    assert(max(List(31,2,3,-31,1,2,-1,0,24,1,21,22)) === 31)
    assert(max(List(2,31,3,-31,1,2,-1,0,24,1,21,22)) === 31)
    assert(max(List(2,3,-31,1,2,-1,0,24,1,21,22,31)) === 31)
    assert(max(List(Int.MaxValue,2,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,22)) === Int.MaxValue)
  }

回答by tejas

list.sortWith(_ > ).head & list.sortWith(> _).reverse.head for greatest and smallest number

list.sortWith(_ > ).head & list.sortWith(> _). reverse.head最大和最小数

回答by Bilal Wahla

If you are required to write a recursive max function on a list using isEmpty, head and tail and throw exception for empty list:

如果需要使用 isEmpty、head 和 tail 对列表编写递归 max 函数并为空列表抛出异常：

def max(xs: List[Int]): Int =
  if (xs.isEmpty) throw new NoSuchElementException("max of empty list")
  else if (xs.tail.isEmpty) xs.head
  else if (xs.head > xs.tail.head) max(xs.head :: xs.tail.tail)
  else max(xs.tail)

if you were to use max function on list it is simply (you don't need to write your own recursive function):

如果您要在列表中使用 max 函数，它很简单（您不需要编写自己的递归函数）：

val maxInt = List(1, 2, 3, 4).max