Unterstützt Scala die Tail Recursion-Optimierung?

Question

Unterstützt Scala die Tail Recursion-Optimierung?

Answer 1

Scala führt die Tail Recursion-Optimierung zur Kompilierzeit durch, wie andere Poster gesagt haben. Das heißt, eine rekursive Tail-Funktion wird vom Compiler in eine Schleife umgewandelt (ein Methodenaufruf wird in einen Sprung umgewandelt), wie aus der Stack-Kurve ersichtlich ist, wenn eine rekursive Tail-Funktion ausgeführt wird.

Versuchen Sie, die folgenden Ausschnitt:

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

und die Stack-Trace inspizieren. Es wird nur einen Aufruf an den Funktions-Boom angezeigt - daher ist der kompilierte Bytecode nicht rekursiv.

Es gibt einen Vorschlag, der zu implement tail calls at the JVM level schwebt - was meiner Meinung nach eine großartige Sache wäre, denn dann könnte die JVM Laufzeitoptimierungen durchführen, anstatt nur die Zeitoptimierungen des Codes zu kompilieren - und könnte möglicherweise einen flexibleren Tail bedeuten Rekursion. Grundsätzlich würde sich ein tailcall invoke genau wie eine normale Methode invoke verhalten, wird aber den Stack des Aufrufers fallen lassen, wenn es sicher ist - die Spezifikation der JVM besagt, dass Stack-Frames beibehalten werden müssen, also muss das JIT eine statische Codeanalyse durchführen Finde heraus, ob die Stack Frames niemals benutzt werden.

Der aktuelle Status ist es proto 80%. Ich denke nicht, dass es rechtzeitig für Java 7 gemacht wird (invokedynamic hat eine höhere Priorität, und die Implementierung ist fast abgeschlossen), aber Java 8 könnte es implementiert sehen.

Answer 2

Nur in sehr einfachen Fällen, in denen die Funktion selbstrekursiv ist.

Proof of tail recursion ability.

Es ist wie Scala sieht 2.8 könnte Schwanz-Rekursion Anerkennung sein zu verbessern, though.

Answer 3

Scala 2.7.x unterstützt Tail-Call-Optimierung für Selbstrekursion (eine Funktion, die sich selbst aufruft) der finalen Methoden und lokalen Funktionen.

Scala 2.8 könnte auch mit Bibliotheksunterstützung für Trampolin geliefert werden, was eine Technik zur Optimierung gegenseitig rekursiver Funktionen ist.

Eine Menge Informationen über den Zustand der Scala Rekursion finden Sie in Rich Dougherty's blog.

Answer 4

In Scala 2.8 können Sie @tailrec verwenden spezifische Methode zu markieren, die Sie der Compiler hoffentlich optimieren:

import scala.annotation.tailrec 

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

Wenn eine Methode Sie eine Warnung nicht optimiert werden kann.