如何使用TailCalls？

Question

如果我理解正确，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 

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

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

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

Answer 1

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

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

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

Answer 2

这个问题已经有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 的一大用例是做一些类似右折叠的事情。