如何使用 TailCalls? [英] How to use TailCalls?

问题描述

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

If I understand correctly, scala.util.control.TailCalls can be used to avoid stack overflows for non-tail-recursive functions by using a trampoline. The example given in the API is straightforward:

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 

然而，更有趣的情况是如果你想在递归调用之后做一些操作.我以某种方式运行了一个天真的"阶乘实现

However, the more interesting case is if you want to do some operations after the recursve call. I got a "naive" factorial implementation somehow running by

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

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

but this looks horrible and I doubt that this is the intended use. So my question is how to write a factorial or fibonacci function correctly using TailCalls (yes, I know how to use accumulators to get them tail-recursive)? Or is TailCalls not suitable for this kind of problem?

推荐答案

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

Yes, your naive factorial will not be tail recursive, and will use stack space linear in the value of the argument. The purpose of scala.util.control.TailCalls is not to magically turn non-tail-recursive algorithms into tail recursive ones. It's purpose is to allow cycles of mutually tail-called functions to execute in constant stack space.

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

The Scala compiler implements tail-recursion optimization for methods which call themselves in tail position, allowing the stack frame of the calling method to be used by the caller. It does this essentially by converting a provably tail-recursive call to a while-loop, under the covers. However, due to JVM restrictions there's no way for it to implement tail-call optimization, which would allow any method call in tail position to reuse the caller's stack frame. This means that if you have two or more methods that call each other in tail position, no optimization will be done, and stack overflow will be risked. scala.util.control.TailCalls is a hack that allows you to work around this problem.

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

BTW, It's well worth looking at the source to scala.util.control.TailCalls. The "result" call is where all the interesting work gets done, and it's basically just a while loop inside.

这篇关于如何使用 TailCalls?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！