Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.7k views
in Technique[技术] by (71.8m points)

scala - How do I make a function involving futures tail recursive?

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."

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)
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.

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.

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

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)

}

And the output is:

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)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...