20

如果我理解正确， scala.util.control.TailCalls 可用于通过使用蹦床来避免非尾递归函数的堆栈溢出。API 中给出的示例很简单：

import scala.util.control.TailCalls._

def isEven(xs: List[Int]): TailRec[Boolean] =
   if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))

def isOdd(xs: List[Int]): TailRec[Boolean] =
   if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

isEven((1 to 100000).toList).result

但是，更有趣的情况是，如果您想在 recurve 调用之后进行一些操作。我得到了一个“天真的”阶乘实现以某种方式运行

def fac(n:Long): TailRec[Long] = 
    if (n == 0) done(1) else done(n * tailcall(fac(n - 1)).result)

但这看起来很可怕，我怀疑这是预期用途。所以我的问题是如何使用 TailCalls 正确编写阶乘或斐波那契函数（是的，我知道如何使用累加器使它们尾递归）？还是 TailCalls 不适合这种问题？

4

2 回答 2

28

是的，您的天真阶乘不会是尾递归的，并且会在参数值中使用线性堆栈空间。scala.util.control.TailCalls 的目的不是神奇地将非尾递归算法转换为尾递归算法。其目的是允许相互尾调用函数的循环在恒定堆栈空间中执行。

Scala 编译器对在尾部位置调用自身的方法实现尾部递归优化，允许调用者使用调用方法的堆栈帧。它本质上是通过在幕后将可证明的尾递归调用转换为 while 循环来实现的。但是，由于 JVM 的限制，它无法实现尾部调用优化，这将允许尾部位置的任何方法调用重用调用者的堆栈帧。这意味着如果您有两个或多个在尾部位置相互调用的方法，则不会进行任何优化，并且会有堆栈溢出的风险。scala.util.control.TailCalls 是一个 hack，可以让你解决这个问题。

顺便说一句，非常值得查看 scala.util.control.TailCalls 的源代码。“结果”调用是完成所有有趣工作的地方，它基本上只是内部的一个 while 循环。

于 2010-12-13T12:55:09.967 回答
5

这个问题已经超过 6 年了，但接受的答案似乎没有回答这个问题：

所以我的问题是如何使用 TailCalls 正确编写阶乘或斐波那契函数（是的，我知道如何使用累加器使它们尾递归）？

所以，这里是：

object Factorial {

  /**
    * Returns the nth factorial
    */
  def apply(n: Long): BigInt = {
    if (n < 0)
      throw new IllegalArgumentException("Can't factorial to an index less than 0")
    else {
      import scala.util.control.TailCalls._
      def step(current: Long): TailRec[BigInt] = {
        if (current <= 0)
          done(1)
        else
          tailcall {
            for {
              next <- step(current - 1)
            } yield current * next
          }
      }
      step(n).result
    }
  }

}

assert(Factorial(0) == 1)
assert(Factorial(7) == 5040)
assert(Factorial(10) == 3628800)

使用 TailCalls 的一大用例是做一些类似右折叠的事情。

于 2016-08-28T15:21:47.550 回答