scala – 如何使用TailCalls？

发布时间：2020-12-16 09:37:18 所属栏目：安全来源：网络整理

导读：如果我理解正确，那么可以使用scala.util.control.TailCalls来避免使用蹦床的非尾递归函数的堆栈溢出。 API中给出的示例很简单： import scala.util.control.TailCalls._def isEven(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty) done(true) else tai

如果我理解正确，那么可以使用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不适合这种问题？

解决方法

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

Scala编译器为尾部位置调用自身的方法实现了尾递归优化，允许调用方使用调用方法的堆栈帧。它基本上通过将封闭式的可循环递归调用转换为while循环来实现。然而，由于JVM限制，没有办法实现尾调用优化，这将允许任何方法调用尾部位置来重用调用者的堆栈帧。这意味着如果您有两个或更多的方法在尾部位置相互调用，则不会进行优化，堆栈溢出将面临风险。 scala.util.control.TailCalls是一个黑客，可以让你解决这个问题。

BTW，非常值得一看scala.util.control.TailCalls的来源。 “结果”调用是所有有趣的工作完成的地方，它基本上只是一段时间的循环。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!