scala - 如何使用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 

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

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是一种可让您解决此问题的技巧。

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