在斯卡拉

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部门中没有人会抱怨尾部递归:-)