Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
End rekursion tail call in java nicht möglich???
Hallo, ich beschäftige mich gerade mit Endrekursion. Nun unterstütz wohl java gar keine Endrekursion wenn ich das richtig in erfahrung gebracht habe.
Stimmt das? heißt das ich hab in java im ungünstigsten Fall immer ein Stack overflow auch wenn ich endrekursiv programmiere? habe mal folgendes Beispiel, das müsste wenn ich richtig verstanden hab endrekursiv sein, da ja mit dem Funktionsaufruf keine Berechnugn einhergeht.
also eigentlich müsst das programm ja endloss laufen wenn es tail recursion in java gäbe, tut es aber nicht. Hab ich das beispiel falsch programmiert oder ist es tatsächlich so das Java keine Endrekursion unterstützt?
public class Stack{
public static void main(String[] args){
stack(1000);
}
public static int stack(int n){
System.out.print(n);
return stack(n);
}
}
Endrekursion in Java ist möglich, allerdings wird die JVM keine Optimierung vornehmen. Das heißt, du kannst auch für einen endrekursiven Algorithmus einen StackOverflowError bekommen. [0]
In deinem konkreten Beispiel fehlt die Abbruchbedingung, deshalb bekommst du immer einen StackOverflowError: Es wird die Zahl “1000” so oft ausgegeben bis der Stack voll ist (Da die JVM die Endrekursion nicht optimiert). Mit Abbruchbedinung würde das Beispiel funktionieren, allerdings wirst du auch dann einen StackOverflowError für (zu) große n bekommen.
Korrekt wäre:
public class Stack{
public static void main(String[] args){
stack(1000);
}
public static int stack(int n){
if (n < 0) return 0; // Abbruchbedingung!
System.out.print(n);
// Das "Problem" wird verkleinert. Es sollen nicht mehr die Zahlen von
// n bis 0 ausgegeben werden, sondern nur noch von n-1 bis 0.
return stack(n - 1);
}
}Ein endrekursiver Algorithmus für die Summe der Zahlen 1 bis n:
public class Stack{
public static void main(String[] args){
int s = sum(1000, 0);
}
public static int sum(int n, int accumulator){
if (n <= 0) return accumulator;
return sum(n - 1, accumulator + n);
}
}Ein nicht endrekursiver Algorithmus für die Summe der Zahlen 1 bis n:
public class Stack{
public static void main(String[] args){
int s = sum(1000);
}
public static int sum(int n){
if (n <= 0) return 0;
return n + sum(n - 1);
}
}Ein endrekursiver Algorithmus benötigt meistens einen Parameter, in dem das Zwischenergebnis abgelegt wird. In dem Beispiel ist das der Parameter “accumulator”.
[0] http://stackoverflow.com/questions/3616483/why-does-the-jvm-still-not-support-tail-call-optimization
Hmm ok das mein ich ja das mit der Optimierung. Ist die endrekursive Funktion die du geschrieben hast, dann lediglich ein “emulierte” Endrekursion oder ist es dabei tatsächlich so das also kein neues Stack aufgemacht wird? oder würde diese irgendwann auch ein Stackoverflow erzeugen bei Werten die groß genug wären, da bei jedem rekursiven aufruf ein neues Stack aufgebaut wird?
==> return sum(n - 1, accumulator + n); <== also würde hier trotzdem von der JVM eine neues Stack aufgemacht, weil keine Optimierung stattfindet, oder läuft das tatsächlich im selben Stack?
[url=http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations]http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations[/url]
1 Like
Ein Thread in der JVM hat genau einen Stack. Der Stack enthält die lokalen Variablen der Methoden (Das ist nicht ganz exakt, aber reicht im Moment als Erklärung aus). Zu den lokalen Variablen gehören natürlich auch die Parameter, die der Methode übergeben werden.
Wenn die Methode “main” betreten wird, enthält der Stack also die Parameter der Methode (String[] args) und die anderen lokalen Variablen (in diesem Fall keine):
Stack: [main_0: args]Wenn die Methode “sum” aufgerufen wird, werden hinter den Variablen der Methode “main” die Variablen der Methode “sum” gespeichert:
Stack: [main_0: args] [sum:0: n]Die Methode sum ruft sich selber wieder auf, deshalb müssen die lokalen Variablen des zweiten Aufrufs wieder an den Stack angehängt werden:
Stack: [main_0: args] [sum_0: n] [sum_1: n]Das passiert so lange, bis die Methode “sum” sich nicht erneut selber aufruft. Wenn der Aufruf “sum_1” den Trivialfall erreicht hat und 0 zurückgibt, kann der entsprechende Teil des Stacks entfernt werden:
Stack: [main_0: args] [sum_0: n]Der Stack enthält jetzt nur noch den Aufruf main_0 und sum_0, da der Aufruf sum_1 eben die Funktion durch ein return beendet hat. In Java wird auch für endrekursive Funktionen für jeden erneuten Aufruf Platz auf dem Stack benötigt, da Java Endrekursion nicht optimiert.
In einer JVM, die Endrekursion optimieren würde, würde der Aufruf sum_0 von dem Stack entfernt werden und durch den Aufruf sum_1 ersetzt:
Stack: [main_0: args]
Stack: [main_0: args] [sum_0: n]
Stack: [main_0: args] [sum_1: n]In dieser JVM würde ein Aufruf von “sum” auch für sehr große n keinen StackOverflowError werfen, da immer nur ein Aufruf von “sum” auf dem Stack liegt.
Der Stack für den Aufruf von “sum(int n, int a)” für n=4 und a=0 (a ist der accumulator) würde folgendermaßen aussehen:
Stack: [main_0: args]
Stack: [main_0: args] [sum_0: n=4 a=0]
Stack: [main_0: args] [sum_0: n=4 a=0] [sum_1: n=3 a=4]
Stack: [main_0: args] [sum_0: n=4 a=0] [sum_1: n=3 a=4] [sum_2: n=2 a=7]
Stack: [main_0: args] [sum_0: n=4 a=0] [sum_1: n=3 a=4] [sum_2: n=2 a=7] [sum_3: n=1 a=9]
Stack: [main_0: args] [sum_0: n=4 a=0] [sum_1: n=3 a=4] [sum_2: n=2 a=7] [sum_3: n=1 a=9] [sum_4: n=0 a=10]Wenn die Endrekursion optimiert werden würde, könnte der Stack so aussehen:
Stack: [main_0: args]
Stack: [main_0: args] [sum_0: n=4 a=0]
Stack: [main_0: args] [sum_1: n=3 a=4]
Stack: [main_0: args] [sum_2: n=2 a=7]
Stack: [main_0: args] [sum_3: n=1 a=9]
Stack: [main_0: args] [sum_4: n=0 a=10]Super. Danke für die ausführliche Antwort.
Grüße