Est-ce que Scala supporte l’optimisation de la récursion de la queue?

Est-ce que Scala supporte l’optimisation de la récursion de la queue?

Scala effectue l’optimisation de la récursion de la queue à la compilation, comme d’autres affiches l’ont dit. C’est-à-dire qu’une fonction récursive de queue est transformée en une boucle par le compilateur (une méthode appelée est transformée en saut), comme on peut le voir depuis la trace de la stack lors de l’exécution d’une fonction récursive de queue.

Essayez l’extrait suivant:

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

et inspectez la trace de la stack. Il affichera un seul appel à la fonction boom - par conséquent, le bytecode compilé n'est pas récursif.

Il y a une proposition qui circule pour implémenter les appels de queue au niveau de la JVM - ce qui à mon avis serait une bonne chose, car la JVM pourrait faire des optimisations à l'exécution plutôt que de simplement comstackr les optimisations du code - récursion flexible de la queue. Fondamentalement, un tailcall invoke type " tailcall invoke se comporterait exactement comme une méthode normale invoke mais abandonnera la stack de l'appelant lorsque cela ne tailcall invoke - la spécification de la machine virtuelle JVM stipule que pour savoir si les frameworks de stack ne seront jamais utilisés.

Son statut actuel est proto 80% . Je ne pense pas que cela sera fait à temps pour Java 7 ( invokedynamic a une plus grande priorité, et l'implémentation est presque terminée) mais Java 8 pourrait le voir implémenté.

Dans Scala 2.8, vous pouvez utiliser @tailrec pour marquer une méthode spécifique que vous espérez que le compilateur optimisera:

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

Si une méthode ne peut pas être optimisée, vous recevez un avertissement.

Scala 2.7.x prend en charge l’optimisation de l’appel de queue pour l’auto-récursion (une fonction appelant elle-même) des méthodes finales et des fonctions locales.

Scala 2.8 peut également être compatible avec le trampoline, une technique permettant d’optimiser les fonctions récursives.

Vous trouverez de nombreuses informations sur l’état de la récursion Scala dans le blog de Rich Dougherty .

Seulement dans des cas très simples où la fonction est auto-récursive.

Preuve de la capacité de récursion de la queue.

Il semblerait que Scala 2.8 améliore la reconnaissance de la récursion de la queue.