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

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

JVM 对尾调用消除的支持是有限的。

我不能谈论 F# 实现，但在 Scala 中你有嵌套调用，所以它不在尾部位置。最简单的思考方式是从堆栈的角度来看：在进行递归调用时，堆栈是否还需要 'remember' 任何其他信息？

在嵌套调用的情况下显然是这样，因为内部调用必须在计算之前完成 'goes back' 并完成外部调用。

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 2

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

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

Answer 3

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

这在使用 CPS 或 monadic 样式等高级功能模式时确实存在问题。为避免炸毁堆栈，您需要在主题上使用 Trampolines. It works but this is neither as convenient nor efficient as proper tail-call optimisation. Edward Kmett's comments 是一个很好的阅读。

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

Is this definition of a tail recursive fibonacci function tail-recursive?

f#

functional-programming

scala

tail-recursion

continuation-passing