Как рекурсивно найти самый большой элемент в списке целых чисел?

Проще всего было бы использовать функцию max признака TraversableOnce следующим образом:

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

Чтобы защититься от пустоты, вы можете сделать что-то вроде этого,

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

Выше даст вам Option[Int]

Мой второй подход будет использовать foldLeft

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

Или если вы знаете значение по умолчанию, которое будет возвращено в случае пустого списка, это станет более простым.

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

В любом случае, поскольку ваше требование состоит в том, чтобы сделать это рекурсивным способом, я предлагаю следуя,

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

Или, как вариант по умолчанию,

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

Обратите внимание, что это tail recursive. Поэтому стек также сохраняется.

Если вы хотите функциональный подход к этой проблеме, то используйте reduceLeft:

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

Эта функция специфична для списка int, если вам нужен более общий подход, то используйте Ordering typeclass:

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

reduceLeft это функция более высокого порядка, которая принимает функцию типа (A, A) => A, в этом случае она берет два Инта, сравнивает их и возвращает больший.

Вы можете использовать сопоставление шаблонов, как это

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
}

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

Обновил свое решение до хвостового рекурсивного благодаря предложениям.

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

Я использовал только 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
    }
  }

Вот тест:

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

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

(это решение не создает экземпляр Option каждый раз. Кроме того, она является хвостовой рекурсивной и будет такой же быстрой, как императивное решение.)

Похоже, вы только начинаете со scala, поэтому я пытаюсь дать вам самый простой ответ на ваш ответ, как это сделать рекурсивно:

 def max(xs: List[Int]): Int = {
   def maxrec(currentMax : Int, l: List[Int]): Int = l match {
     case Nil => currentMax
     case head::tail => maxrec(head.max(currentMax), tail) //get max of head and curretn max
   }
   maxrec(xs.head, xs)
 }

Этот метод определяет собственный внутренний метод (maxrec), чтобы заботиться о рекурсивности. Он потерпит неудачу (исключение), если вы дадите ему пустой список (в пустом списке нет максимума)

Вот мой код (я новичок в функциональном программировании), и я предполагаю, что тот, кто попадет под этот вопрос, будет таким же, как я. Лучший ответ, хотя и отличный, немного слишком много для новичков, чтобы принять! Итак, вот мой простой ответ. Обратите внимание, что меня попросили (в рамках курса) сделать это, используя только голову и хвост.

/**
   * 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)

Некоторые тесты:

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

Список.sortWith(_ > ).глава и список.sortWith( > _).обратный.голова для наибольшего и наименьшего числа

Если требуется написать рекурсивную функцию max в списке, используя isEmpty, head and tail и исключение throw для пустого списка:

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)

Если вы хотите использовать функцию max в списке, это просто (вам не нужно писать свою собственную рекурсивную функцию):

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

def max(xs: List[Int]): Int = {
  def _max(xs: List[Int], maxAcc:Int): Int = {
    if ( xs.isEmpty ) 
      maxAcc 
    else 
      _max( xs.tail, Math.max( maxAcc, xs.head ) ) // tail call recursive
  }

  if ( xs.isEmpty ) 
    throw new NoSuchElementException() 
  else 
    _max( xs, Int.MinValue );
}

С хвостовой рекурсией

  @tailrec
  def findMax(x: List[Int]):Int =  x match {
    case a :: Nil => a
    case a :: b :: c =>  findMax( (if (a > b) a else b) ::c)
  }

 def max(xs: List[Int]): Int = xs match {
    case Nil => throw new NoSuchElementException("empty list!")
    case x :: Nil => x
    case x :: tail => if (x > max(tail)) x else max(tail)
  }