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

Question

我看到以下这个 F# 的 continuation-passing-style 斐波那契函数定义，我一直认为它是尾递归的：

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，并被告知递归调用不在尾部位置。

  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#的等价，那么为什么这个函数不是尾递归呢？

- devoured elysium

Answer 1

第四行对go的第二次调用并不处于尾部位置，它被包裹在一个匿名函数中。（对于该函数来说，它是尾部位置，但对于go本身来说则不是。）

在传递样式中，你需要Proper Tail Calls，而Scala不幸地没有这个功能。（为了在JVM上提供PTCs，需要管理自己的堆栈而不是使用JVM调用堆栈，这会破坏与其他语言的互操作性，然而，互操作性是Scala的主要设计目标。）

- Jörg W Mittag

---

在这种情况下，很容易找到不需要 CPS 的斐波那契函数的替代实现。那么，我该如何在二叉搜索树中实现 max / sum 函数呢？除了使用一个朴素的递归实现之外，我唯一看到的方法就是使用一个栈（deque）。你对此有什么想法吗？ - devoured elysium

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)
}

- melps

Answer 3

很遗憾，JVM目前还不支持尾递归优化（公平地说，有时它可以优化一些调用）。Scala通过程序转换实现尾递归优化（每个尾递归函数等效于一个循环）。这通常足够简单的递归函数，但相互递归或续传风格需要完全优化。

当使用高级函数模式如CPS或单子样式时，这确实是一个问题。为了避免堆栈溢出，您需要使用Trampolines。它可行，但既不方便也不高效如适当的尾递归优化。Edward Kmett's comments在这个主题上是一个好的阅读。

- Christophe Calvès