Scala 中的尾递归函数在查找第 n 个斐波那契数时出错

Question

我想实现尾递归函数以获得第 n 个斐波那契数。

这是我的尝试。对于 n = 4 或更高版本，它无法正常工作。

object Fibonacci {
    def fib(n: Int): Int = {
        def go(n: Int, acc: Int): Int =
            if (n <= 1) 0 + acc
            else if (n == 2) 1 + acc
            else go(n-1, go(n-2, 0))
        go(n, 0)
    }
}

问题是，虽然输入 n = 3 给出了所需的输出 1，但输入 n = 4 或以上仍然只有 returns 1.

我注意到，如果我定义另一行 "else if"，即 else if (n == 3) 1 + acc，那么我的函数将按预期工作 n = 4（它会按预期 return "2"），但它仍然不适用于 n = 5 或更高版本，我不能找出原因。

如果您觉得我解决问题的方法很奇怪，那是因为这是我目前所学的全部内容，应该足以解决手头的问题。

其实我也不是很确定上面的函数是不是尾递归的，因为我才刚开始学。如果不是，请向我指出，我会进行适当的更改。

Answer 1

您的代码不是尾递归的，因为它在最里面的 go() 调用中构建了一个堆栈。

解决方案是将帮助器展平以同时包括前两个项（而不只是单个项）：

def fib(n : Int) : Int = { 
  def go(n: Int, acc:Int, x:Int): Int = n match {
    case 0 => acc 
    case _ => go(n-1, x, acc+x)
  }
  return go(n, 0, 1)
}

Answer 2

你的问题是在n>2的情况下，你没有使用'acc'参数。

当你调用 go(4,0) 时，你将得到：go(3, go(2,0))

go(2,0) 解析为 1，所以你调用 go(3,1)，它变成 go(2, go(1,0))

go(1,0) resovles 为 0，所以你调用 go(2,0)，其中 returns 1.

您需要阅读最后一个案例：go(n-1, go(n-2, acc))

正如其他人所指出的，您的函数不是尾递归的，因为调用 go(n-2, 0) 的结果用于另一个函数调用。如果您打算制作尾递归函数，请使用“@tailrec”注释，这样当您的函数不是尾递归时编译器会给您一个错误。

Richard 的解决方案通过运行循环中的两个累加器来工作：当前总计和先前总计，最后取出其中一个，从而允许函数正确地进行尾递归。

Answer 3

此解决方案始终return n 斐波那契数而不是 n+1 斐波那契数。

def fibonacci (n: Int): Int = {

    @tailrec
    def go(nextToLast: Int, last: Int, n: Int): Int = n match {
        case 0 => 0
        case 1 => last
        case _ => go(last, nextToLast+last, n-1)
    }
    go(0, 1, n-1)
}

希望能帮到你

Scala 中的尾递归函数在查找第 n 个斐波那契数时出错

Error in tail-recursion function in Scala to find nth Fibonacci number

scala

fibonacci

tail-recursion