¿Scala es compatible con la optimización de recursividad de cola?

¿Scala es compatible con la optimización de recursividad de cola?

    Scala realiza la optimización de la recursividad en tiempo de comstackción, como han dicho otros carteles. Es decir, el comstackdor transforma una función recursiva de cola en un bucle (una invocación de método se transforma en un salto), como se puede ver en el seguimiento de stack cuando se ejecuta una función recursiva de cola.

    Prueba el siguiente fragmento:

    def boom(n: Int): Nothing = if(n< =0) throw new Exception else boom(n-1) boom(10) 

    e inspecciona el rastro de la stack. Mostrará solo una llamada al auge de funciones, por lo tanto, el bytecode comstackdo no es recursivo.

    Hay una propuesta flotando para implementar llamadas finales a nivel de JVM , lo que en mi opinión sería una gran cosa, ya que la JVM podría hacer optimizaciones de tiempo de ejecución, en lugar de solo comstackr optimizaciones de tiempo del código, y posiblemente podría significar más recursividad de cola flexible. Básicamente, una tailcall invoke se comportaría exactamente como una invoke método normal, pero abandonará la stack de la llamada cuando sea seguro hacerlo: la especificación de la JVM establece que las estructuras de stack deben conservarse, por lo que el JIT debe realizar un análisis de código estático para averiguar si los marcos de stack nunca serán utilizados.

    El estado actual es proto 80% . No creo que se haga a tiempo para Java 7 ( invokedynamic tiene una mayor prioridad, y la implementación está casi lista) pero Java 8 podría verlo implementado.

    En Scala 2.8 puede usar @tailrec para marcar el método específico que espera que el comstackdor optimice:

     import scala.annotation.tailrec @tailrec def factorialAcc(acc: Int, n: Int): Int = { if (n < = 1) acc else factorialAcc(n * acc, n - 1) } 

    Si un método no puede optimizarse, recibe una advertencia.

    Scala 2.7.x es compatible con la optimización de la cola de llamadas para la auto-recursión (una función que se llama a sí misma) de los métodos finales y las funciones locales.

    Scala 2.8 podría venir con soporte de biblioteca para trampolín también, que es una técnica para optimizar funciones mutuamente recursivas.

    Se puede encontrar una gran cantidad de información sobre el estado de la recurrencia de Scala en el blog de Rich Dougherty .

    Solo en casos muy simples en que la función es auto recursiva.

    Prueba de la capacidad de recursión de la cola.

    Sin embargo, parece que Scala 2.8 podría estar mejorando el reconocimiento de recursividad de cola.