scala - 函数式编程: recursive loop output fibonacci sequence in scala

Question

使用 scala 学习函数式编程。遇到了这个练习。

编写一个递归函数来获取第 n 个斐波那契数 ( http://mng.bz/C29s )。前两个斐波那契数是 0 和 1。第 n 个数始终是前两个数的和 - 序列从 0、1、1、2、3、5 开始。您的定义应使用局部尾递归函数。

def fib(n: Int): Int

我的答案计算 n+1 个值并返回第 n 个。谁能告诉我一个更好的实现，其中不计算额外的第 n+1 个值？

object patterns {

    def fib(n : Int): Int = {
        @annotation.tailrec
        def go(n: Int, prev2: Int, prev: Int): Int =
            if(n<=0) prev2 
            else go(n-1, prev, prev2+prev)
        go(n, 0, 1)
      }
}

如果有人感兴趣，这是 Chiusano 和 Bjarnason 所著的《scala 函数式编程》一书。练习2.1 期待您的回复。

Answer 1

我认为:

def fib2(n: Int): Int = {
  if (n < 1) 0
  else if (n < 2) 1
  else {
    @annotation.tailrec
    def go(i: Int, prev2: Int, prev: Int): Int =
      if (i == n) prev
      else go(i + 1, prev, prev2 + prev)
    go(2, 1, 1)
  }
}

或使用 ByName 参数:

def fib3(n: Int): Int = {
  @annotation.tailrec
  def go(n: Int, prev2: Int, prev: => Int): Int =
    //                            ^ ByName
    if (n <= 0) prev2
    else {
      val p = prev
      go(n - 1, p, prev2 + p)
    }
  go(n, 0, 1)
}