在斯卡拉

Question

誤服實現斐波那契序列在斯卡拉聚會，我們正在討論的處事「Scala的方式」 ......

有人問不同的開發商如何，他/她將實現在斯卡拉Fibonacci序列。 ..用下面的代碼回答的人（只被告知，雖然它的工作，這是不是最佳）：

def fibonacci(n: Int):BigInt = n match { 
    case 0 => 0 
    case 1 => 1 
    case _ => fibonacci(n - 1) + fibonacci(n - 2) 
} 

1. 有什麼不對這種方法嗎？

2. 有什麼方法可以改善這個代碼，斯卡拉方式？

Answer 1

這個人會不止一次地計算出許多子問題。 您可以將算法看作一棵樹。

例如，如果你問fibonacci(4)你算算：

fib(4) = fib(3) + fib(2) = 2 + 1 = 3 
    // left subtree: 
    fib(3) = fib(2) + fib(1) = 1+1 = 2 
    // left 
    fib(2) = fib(1) + fib(0) = 0+1 = 1 
    // right 
    fib(1) = 1 
    // right 
    fib(2) = fib(1) + fib(0) = 0+1 = 1 

，你可以看到你計算fib(2) 2倍，這隻會變得更糟在更高的數字。

至於如何改善這種代碼：

• 無論是從動態編程memoize的值
• 使用技術（以及它或多或少的memoization太）
• 或使用更好的算法！

有關於這一主題在這裏的許多問題已經 - 從這裏開始：Efficient calculation of Fibonacci series

或者看看這個問題的具體斯卡拉 - 答案：What is the fastest way to write Fibonacci function in Scala?

Answer 2

與功能的問題，如所描述是非尾遞歸調用。這意味着這裏涉及的遞歸需要一個棧來工作（在你的示例中，它是調用棧）。換句話說，該功能大致相當於：

import scala.collection.mutable.Stack 

def fibonacci(n: Int): BigInt = { 
    var result = BigInt(0) 
    val stack = Stack.empty[Int] 
    stack.push(n) 

    while (stack.nonEmpty) { 
    val x = stack.pop() 
    if (x == 1) { 
     result += 1 
    } 
    else if (x > 1) { 
     stack.push(x - 2) 
     stack.push(x - 1) 
    } 
    } 

    result 
} 

正如你所看到的那樣，這不是很有效率嗎？在每次迭代中，堆棧的大小都會增加一個，因爲您可以查看樹形調用，這將是一個合適的binary tree，其大小取決於N以及其上的樹葉數大約爲2 ^N（實際上較少但是當N很大時常數因子並不重要），所以我們討論的是O（2 ^N）時間複雜度和O（n）存儲器複雜度（即所需堆棧大小爲N）。現在這是exponential growth時間和使用的內存線性增長。這意味着需要花費很長時間來處理，而且它使用的內存比應該多。順便說一下，作爲一個軟件開發人員，推薦Big O notation是個不錯的主意，因爲這是您在談論性能或內存消耗時首先需要考慮的事情。

謝天謝地，對於斐波那契我們不需要遞歸。這是一個更高效的實現：

def fibonacci(n: Int): BigInt = { 
    var a = BigInt(0) 
    var b = BigInt(1) 
    var idx = 0 

    while (idx < n) { 
    val tmp = a 
    a = b 
    b = tmp + a 
    idx += 1 
    } 

    a 
} 

這只是一個簡單的循環。它不需要堆棧工作。內存複雜度爲O(1)（這意味着它需要一個恆定的內存量才能工作，與輸入無關）。在時間上這個算法是O(n)，大致意味着處理結果涉及到一個涉及N迭代的循環，所以時間的增長取決於輸入N，但是是線性的而不是指數的。

在Scala中，你也可以將此描述爲一個tail recursion：

import annotation.tailrec 

def fibonacci(n: Int): BigInt = { 
    @tailrec 
    def loop(a: BigInt, b: BigInt, idx: Int = 0): BigInt = 
    if (idx < n) 
     loop(b, a + b, idx + 1) 
    else 
     a 

    loop(0, 1) 
} 

這個循環被描述爲一個遞歸函數，但因爲這是一個「尾遞歸調用」，編譯器重寫此功能一簡單的循環。您還可以看到@tailrec註釋的存在。這不是絕對必要的，編譯器會將它優化成沒有它的循環，但是如果你使用這個註解，如果所描述的函數不是尾遞歸，那麼編譯器會出錯 - 這很好，因爲依賴時很容易出錯在尾遞歸上工作（即，你做了一個改變，並且沒有注意到，bam，函數不再是尾遞歸）。使用這個註釋，因爲編譯器可以保護你，如果你這樣做。

因此，在這種情況下，您使用不可變的東西（不再指定更多變量），但它將具有與while循環相同的性能特徵。您喜歡哪個版本，這取決於您的偏好。我更喜歡後者，因爲我更容易發現不變量和退出條件，再加上我喜歡不變性，但其他人更喜歡前者。關於這種做法的慣用方式，您也可以使用懶惰的Stream或Iterable，但FP部門中沒有人會抱怨尾部遞歸:-)