scala: implement a generic recursive max function

Went through a similar exercise as the OP sans pattern matching and generic types, and came up with the following:

def max(xs: List[Int]): Int = {
    if (xs.isEmpty) throw new NoSuchElementException

    if (xs.length == 1) 
        return xs.head 
      else 
        return max(xs.head, max(xs.tail))
  }

  def max(x: Int, y: Int): Int = if (x > y) x else y

I have just come up with this solution.

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

Maybe you want the Ordering type class?

def max[T: Ordering](list: List[T]): T = list match {
  case Nil => throw new RuntimeException("maximum of empty list")
  case head :: Nil => head
  case list =>
    val maxTail = max(list.tail)
    if (implicitly[Ordering[T]].gt(list.head, maxTail)) list.head else maxTail
}

This is, after all, how the built-in max method works:

// From GenTraversableOnce
def max[A1 >: A](implicit ord: Ordering[A1]): A

You can clean things up a lot if you do this:

def max[T](list: List[T])(implicit ord: Ordering[T]): T = list match {
  case Nil => throw new RuntimeException("maximum of empty list")
  case head :: Nil => head
  case head :: tail => ord.max(head, max(tail))
}

Or, you can make it tail-recursive for increased efficiency (because the compiler will optimize it):

def max[T](list: List[T])(implicit ord: Ordering[T]): T = {
  if (list.isEmpty)
    throw new RuntimeException("maximum of empty list")

  @tailrec
  def inner(list: List[T], currMax: T): T =
    list match {
      case Nil => currMax
      case head :: tail => inner(tail, ord.max(head, currMax))
    }
  inner(list.tail, list.head)
}

Also, you should throw RuntimeException or a subclass of it, not Error.