I think an anon function would work, but can't seem to find the proper syntax...

max.scala

// Original....
def max(xs: List[Int]): Int = {
  def findMax(curr: Int, l: List[Int]): Int = {
    if (l.isEmpty)
      curr
    else if (l.head > curr)
      findMax(l.head, l.tail)
    else
      findMax(curr, l.tail)
  }
}  

// Tried to make smaller with this....
def max(xs: List[Int]): Int = {
  def findMax(curr: Int, l: List[Int]): Int = {
    if (l.isEmpty)
      curr
    else
      findMax(if (l.head > curr) l.head curr, l.tail) // <==  How do I do this in Scala?  
                                                      // Can't determine the return type
  }

  findMax(0, xs)
}

Also, the question required we use recursion so I wasn't able to use other methods.

Well, the pattern matching version is recursive, but I understand. :)

Or, if you wanted to be fancy, derive your own fold left. Might be an interesting exercise with types.