¿Cómo puedo hacer que una función que involucre futuros sea recursiva?

En mi aplicación Scala, tengo una función que llama a una función que devuelve un resultado de tipo Futuro [T]. Necesito pasar el resultado mapeado en mi llamada de función recursiva. Quiero que esto sea recursivo de cola, pero el mapa (o flatMap) está rompiendo la capacidad de hacer eso. Me aparece un error “Llamada recursiva no en posición de cola”.

A continuación se muestra un ejemplo simple de este escenario. ¿Cómo se puede modificar esto para que la llamada sea recursiva de cola (sin subvertir los beneficios de Futures con 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  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) 

Podría estar equivocado, pero su función no necesita ser recursiva de cola en este caso.

La recursividad de cola nos ayuda a no consumir la stack en caso de que usemos funciones recursivas. En su caso, sin embargo, en realidad no estamos consumiendo la stack como lo haría una función recursiva típica.

Esto se debe a que la llamada “recursiva” se realizará de forma asincrónica, en algún subproceso del contexto de ejecución. Por lo tanto, es muy probable que esta llamada recursiva ni siquiera resida en la misma stack que la primera llamada.

El método factorialAcc creará el objeto futuro que eventualmente disparará la llamada “recursiva” de forma asíncrona. Después de eso, se saca inmediatamente de la stack.

Así que esto no es realmente recursión de la stack y la stack no crece proporcionalmente a n, permanece aproximadamente en un tamaño constante.

Puede comprobarlo fácilmente lanzando una excepción en algún punto del método factorialAcc e inspeccionando el seguimiento de la stack.

Reescribí tu progtwig para obtener un seguimiento de stack más legible:

 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) } 

Y la salida es:

 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) 

Entonces puedes ver que la stack es realmente corta. Si esto fuera recursión de la stack, debería haber visto aproximadamente 97 llamadas al método factorialAcc . En cambio, solo ves uno.

¿Qué hay de usar foldLeft en su lugar?

 def factorial(n: Int): Future[Int] = future { (1 to n).foldLeft(1) { _ * _ } } 

Aquí hay una solución foldLeft que llama a otra función que devuelve un futuro.

 def factorial(n: Int): Future[Int] = (1 to n).foldLeft(Future.successful(1)) { (f, n) => f.flatMap(a => getFutureNumber(n).map(b => a * b)) } def getFutureNumber(n: Int) : Future[Int] = Future.successful(n) 

Haz que factorialAcc devuelva un Int y solo lo envuelva en un futuro en la función factorial .

 def factorial(n: Int): Future[Int] = { @tailrec def factorialAcc(acc: Int, n: Int): Int = { if (n <= 1) { acc } else { factorialAcc(n*acc,n-1) } } future { factorialAcc(1, n) } } 

probablemente debería funcionar