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

Question

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

Answer 1

Scala realiza la optimización de recursión de cola en tiempo de compilación, como han dicho otros carteles. Es decir, el compilador 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 pila 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 inspeccione el seguimiento de la pila. Mostrará solo una llamada al auge de funciones, por lo tanto, el bytecode compilado no es recursivo.

Hay una propuesta que flota en torno al implement tail calls at the JVM level, lo que en mi opinión sería una gran cosa, ya que la JVM podría optimizar el tiempo de ejecución en lugar de compilar las optimizaciones de tiempo del código, y podría significar una cola más flexible recursividad. Básicamente, un tailcall invoke se comportaría exactamente como un método normal invoke, pero abandonará la pila de la persona que llama cuando sea seguro hacerlo: la especificación de la JVM establece que las estructuras de pila deben conservarse, por lo que el JIT debe realizar un análisis de código estático para averigua si los marcos de pila nunca serán utilizados.

El estado actual de la misma 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.

Answer 2

Solo en casos muy simples en los que la función es autorecitante.

Proof of tail recursion ability.

Parece Scala 2.8 podría ser mejorar el reconocimiento de cola recursividad, sin embargo.

Answer 3

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

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

Se puede encontrar mucha información sobre el estado de la recurrencia de Scala en Rich Dougherty's blog.

Answer 4

En Scala 2.8 se puede utilizar para marcar @tailrec método específico que espera el compilador optimizará:

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 ser optimizado recibe una advertencia.