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

Question

我已经看到了以下F＃定义的延续传递式fibonacci函数，我总是假设是尾递归的：

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＃one，所以我想知道为什么函数不是尾递归的？

Answer 1

第4行第二次调用go不在尾部位置，它包含在匿名函数中。 （它位于该功能的尾部位置，但不适用于go本身。）

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

Answer 2

JVM对尾部呼叫消除的支持是有限的。

我不能说F＃实现，但是在scala中你有嵌套调用，所以它不在尾部位置。考虑它的最简单方法是从堆栈的角度来看：在进行递归调用时，堆栈需要“记住”的其他信息吗？

在嵌套的go调用的情况下，显然是，因为内部调用必须在计算“返回”之前完成并完成外部调用。

可以递归地定义Fib，如下所示：

def fib(k:Int) = {
  @tailrec
  def go(k:Int, p:Int, c:Int) : Int = {
    if(k == 0) p
    else { go(k-1, c p+c) }
  }
  go(k,0 1)
}

Answer 3

不幸的是，JVM还不支持尾调用优化（？）（公平地说，它有时可以优化一些调用）。 Scala通过程序转换实现尾递归优化（每个尾递归函数相当于一个循环）。这通常足以用于简单的递归函数，但是相互递归或延续传递样式需要完全优化。

当使用CPS或monadic风格等高级功能模式时，这确实存在问题。为了避免堆积，你需要使用Trampolines。它可以工作，但这既不像正确的尾调用优化那样方便也不高效。关于这个问题的Edward Kmett's comments是一个很好的阅读。