scala - 这个尾递归斐波那契函数的定义是尾递归的吗？

Question

我已经看到了以下连续传递式斐波那契函数的 F# 定义，我一直认为它是尾递归的:

let fib k =
  let rec fib' k cont =
    match k with
    | 0 | 1 -> cont 1
    | k -> fib' (k-1) (fun a -> fib' (k-2) (fun b -> cont (a+b)))
  fib' k id

在 Scala 中尝试等效代码时，我使用了现有的 @tailrec，当 Scala 编译器通知我递归调用不在尾部位置时，我措手不及:

  def fib(k: Int): Int = {
    @tailrec def go(k: Int, cont: Int => Int): Int = {
      if (k == 0 || k == 1) cont(1)
      else go(k-1, { a => go(k-2, { b => cont(a+b) })})
    }
    go(k, { x => x })
  }

我相信我的 Scala 实现等同于 F# 实现，所以我想知道为什么该函数不是尾递归的？

Answer 1

第 4 行对 go 的第二次调用不在尾部位置，它被包裹在一个匿名函数中。 (它位于 该函数的尾部位置，但不是 go 本身。)

对于连续传递样式，您需要适当的尾调用，不幸的是，Scala 没有。 (为了在 JVM 上提供 PTC，您需要管理自己的堆栈，而不是使用 JVM 调用堆栈，这会破坏与其他语言的互操作性，但是，互操作性是 Scala 的主要设计目标。)