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