3

我已经看到了以下 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#，所以我想知道为什么该函数不是尾递归的？

4

3 回答 3

3

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

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

于 2015-06-23T08:08:30.027 回答
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)
}
于 2015-06-23T08:08:06.237 回答
1

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

这在使用 CPS 或 monadic 样式等高级功能模式时确实存在问题。为避免将堆栈炸毁，您需要使用Trampolines。它可以工作，但这既不像适当的尾调用优化那样方便也不高效。Edward Kmett对这个主题的评论是一本很好的读物。

于 2015-06-23T23:49:34.997 回答