How do I make a function involving futures tail recursive?

by

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.

More Related Contents:

  1. Scala: List[Future] to Future[List] disregarding failed futures
  2. Scala’s “for comprehension” with futures
  3. When to use parenthesis in Scala infix notation
  4. Accessing value returned by scala futures
  5. Use functional combinators on Scala Tuples?
  6. What is the fastest way to write Fibonacci function in Scala?
  7. How can I convert immutable.Map to mutable.Map in Scala?
  8. How to wait for several Futures?
  9. Scala recover or recoverWith
  10. Futures do not run before program termination
  11. Futures / Success race
  12. Scala best way of turning a Collection into a Map-by-key?
  13. Apache Spark – Scala – ReduceByKey – with keys repeating up to twice only
  14. What is the difference between a var and val definition in Scala?
  15. What is the apply function in Scala?
  16. How to import build.gradle into IntelliJ
  17. Scala 2.8 collections design tutorial
  18. Scala classOf for type parameter
  19. val and object inside a scala class?
  20. What are possible reasons for receiving TimeoutException: Futures timed out after [n seconds] when working with Spark [duplicate]
  21. Parsing multiline records in Scala
  22. Why does join fail with “java.util.concurrent.TimeoutException: Futures timed out after [300 seconds]”?
  23. Create new Dataframe with empty/null field values
  24. Get a TypeTag from a Type?
  25. How to write a proper null-safe coalescing operator in scala?
  26. Can’t access Parent’s Members while dealing with Macro Annotations
  27. Why is join not possible after show operator?
  28. Treating an SQL ResultSet like a Scala Stream
  29. Queries with streaming sources must be executed with writeStream.start();
  30. Akka-Stream implementation slower than single threaded implementation

Leave a Comment