如何使涉及期货尾递归的函数? [英] 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 方法将创建 future 对象，该对象最终将异步触发递归"调用.之后，它立即从堆栈中弹出.

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)

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

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屋！