如何做一个包含期货尾部递归的函数？ [英] How do I make a function involving futures tail recursive?

问题描述

在我的Scala应用程序中，我有一个函数调用一个返回Future [T]类型的结果的函数。我需要在递归函数调用中传递映射结果。我希望这是尾递归，但地图（或flatMap）打破了这样做的能力。我收到一个错误递归调用不在尾部位置。

In my Scala app, I have a function that calls a function which returns a result of type Future[T]. I need to pass the mapped result in my recursive function call. I want this to be tail recursive, but the map (or flatMap) is breaking the ability to do that. I get an error "Recursive call not in tail position."

以下是此方案的一个简单示例。这可以如何修改，以便调用是尾递归的（不用Await.result（））颠覆Futures的好处？

Below is a simple example of this scenario. How can this be modified so that the call will be tail recursive (without subverting the benefits of Futures with an Await.result())?

import scala.annotation.tailrec
import scala.concurrent.{Await, Future}
import scala.concurrent.duration._

implicit val ec = scala.concurrent.ExecutionContext.global

object FactorialCalc {
  def factorial(n: Int): Future[Int] = {

    @tailrec
    def factorialAcc(acc: Int, n: Int): Future[Int] = {
      if (n <= 1) {
        Future.successful(acc)

      } else {
        val fNum = getFutureNumber(n)
        fNum.flatMap(num => factorialAcc(num * acc, num - 1))
      }
    }

    factorialAcc(1, n)
  }

  protected def getFutureNumber(n: Int) : Future[Int] = Future.successful(n)
}

Await.result(FactorialCalc.factorial(4), 5.seconds)

推荐答案

我可能会误会，但是在这种情况下，您的函数不需要尾递归。

I might be mistaken, but your function doesn't need to be tail recursive in this case.

尾递归有助于我们不要消耗如果我们使用递归函数堆栈。然而，在你的情况下，我们实际上并不是以典型的递归函数的方式消耗堆栈。

Tail recursion helps us to not consume the stack in case we use recursive functions. In your case, however, we are not actually consuming the stack in the way a typical recursive function would.

这是因为递归调用将异步发生，一些线程从执行上下文。所以很可能这个递归调用甚至不会和第一次调用相同的堆栈。

This is because the "recursive" call will happen asynchronously, on some thread from the execution context. So it is very likely that this recursive call won't even reside on the same stack as the first call.

factorialAcc 方法将创建将来的对象，最终将异步地触发递归调用。之后，它立即从堆栈中弹出。

The factorialAcc method will create the future object which will eventually trigger the "recursive" call asynchronously. After that, it is immediately popped from the stack.

所以这并不是实际的堆栈递归，堆栈不会与n成正比，它大致保持在

So this isn't actually stack recursion and the stack doesn't grow proportional to n, it stays roughly at a constant size.

您可以通过在 factorialAcc 方法中的某一点抛出异常来轻松检查，并检查堆栈跟踪

You can easily check this by throwing an exception at some point in the factorialAcc method and inspecting the stack trace.

我重写了程序以获取更可读的堆栈跟踪：

I rewrote your program to obtain a more readable stack trace:

object Main extends App {
  import scala.concurrent.{Await, Future}
  import scala.concurrent.duration._

  implicit val ec = scala.concurrent.ExecutionContext.global

  def factorialAcc(acc: Int, n: Int): Future[Int] = {

    if (n == 97)
      throw new Exception("n is 97")

    if (n <= 1) {
      Future.successful(acc)

    } else {
      val fNum = getFutureNumber(n)
      fNum.flatMap(num => factorialAcc(num * acc, num - 1))
    }
  }


  def factorial(n: Int): Future[Int] = {
      factorialAcc(1, n)
  }

  protected def getFutureNumber(n: Int) : Future[Int] = Future.successful(n)

  val r = Await.result(factorial(100), 5.seconds)
  println(r)

}

输出是：

Exception in thread "main" java.lang.Exception: n is 97
at test.Main$.factorialAcc(Main.scala:16)
at test.Main$$anonfun$factorialAcc$1.apply(Main.scala:23)
at test.Main$$anonfun$factorialAcc$1.apply(Main.scala:23)
at scala.concurrent.Future$$anonfun$flatMap$1.apply(Future.scala:278)
at scala.concurrent.Future$$anonfun$flatMap$1.apply(Future.scala:274)
at scala.concurrent.impl.CallbackRunnable.run(Promise.scala:29)
at scala.concurrent.impl.ExecutionContextImpl$$anon$3.exec(ExecutionContextImpl.scala:107)
at scala.concurrent.forkjoin.ForkJoinTask.doExec(ForkJoinTask.java:262)
at scala.concurrent.forkjoin.ForkJoinPool$WorkQueue.runTask(ForkJoinPool.java:975)
at scala.concurrent.forkjoin.ForkJoinPool.runWorker(ForkJoinPool.java:1478)
at scala.concurrent.forkjoin.ForkJoinWorkerThread.run(ForkJoinWorkerThread.java:104)

所以你可以看到堆栈实际上很短。如果这是堆栈递归，你应该看到约97个调用 factorialAcc 方法。相反，您只能看到一个。

So you can see that the stack is actually short. If this was stack recursion you should have seen about 97 calls to the factorialAcc method. Instead, you see only one.

这篇关于如何做一个包含期货尾部递归的函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！