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.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…