Wie performance lastig sind rekursionen

[seux]

hallo,

kleine Frage, wie performancelastig sind rekursive Funktionen in Java? Angenommen ich hab eine Funktion, der ein Wert zugewiesen wird. Mit diesem Wert wird dann gerechnet und dann folgt mit dem neuen wert der Rekursionsaufruf, solange, bis eine Abbruchbedingung erreicht wird. Da ich nicht weiß, wie groß die zahl ist, könnte das Argument auch sehr hoch sein, wodurch der Stackframe ziemlich wachsen müsste.

seux

 

[faetzminator]

Wenn du nicht weisst, wie gross die Anzahl Aufrufe können wird, dann ist Rekursion villeicht nicht die beste Lösung. Gibt es einen Grund, warum das nicht iterativ funktioniert?

 

[bLaSt]

Naja es kann unter Umständen verdammt schnell den Rahmen sprängen. Da gibt es auch ein Basic Beispiel dazu was das sehr gut zeigt. Versuch beispielsweise einfach mal die Fibonacci Zahlen rekursiv zu lösen.
Da wirst du schon ganz schnell merken wie schnell es explodiert.

 

[pro2]

Du musst unterscheiden ob du eine endrekursive Funktion hast oder nicht. Bei ersteren tritt dieses Performance Problem nicht auf.
Endrekursion ? Wikipedia

 

[Antoras]

In Java gibt es keine Endrekursion.

 

[HimBromBeere]

Es gibt surchaus Rekursionen, die annähernd genauso schnell ablaufen wie ihre expliziten Äquivalente. Oftmals ist das Umwandeln in eine iterative oder gar eine explizite Form auch gar nicht möglich (sehr kostspieleig), also ist eine pauschale Aussage nur schwierig zu treffen. Hauptargument bleibt aber tatsächlich die Zahl der Widerholungen, die du möglichst gering halten solltest...

 

[Dekker]

In Java gibt es keine Endrekursion.

Erzähl nicht son Käse... Das hat weniger mit der Sprache als mit der Definition der Funktion zu tun.

Es gibt surchaus Rekursionen, die annähernd genauso schnell ablaufen wie ihre expliziten Äquivalente. Oftmals ist das Umwandeln in eine iterative oder gar eine explizite Form auch gar nicht möglich (sehr kostspieleig)

??? Man kann jede rekursive Berechnung auch Iterativ machen. Umgekehrt genauso. Ich verstehe dein Arguement mit "sehr kostspielig" auch nicht. In welchem Kontext bist du da gerade?

..., also ist eine pauschale Aussage nur schwierig zu treffen. Hauptargument bleibt aber tatsächlich die Zahl der Widerholungen, die du möglichst gering halten solltest...

Sowohl die Rekursionstiefe (was du mit der Zahl der Wiederholungen ansprichst) als auch die Anzahl der Argumente und Variablen die eine Funktion hat tragen zum Stackoverflow bei. Desto mehr Argumente und Variablen eine Funktion übergibt bzw. hat, desto mehr Variablen müssen beim rekursiven Aufruf auf den Stack geschrieben werden.

Im allgemeinen gilt eigentlich für Java das man für Fälle in dennen es zur sehr hohen rekursionstiefen kommen kann lieber Iterative Lösungen wählt. Java ist für sich gesehen nicht für rekursion Optimiert. Sowas findet man eher in funktionalen Programmiersprachen wie Lips und Scheme etc. vor.

 

[bLaSt]

Erzähl nicht son Käse... Das hat weniger mit der Sprache als mit der Definition der Funktion zu tun.



??? Man kann jede rekursive Berechnung auch Iterativ machen. Umgekehrt genauso. Ich verstehe dein Arguement mit "sehr kostspielig" auch nicht. In welchem Kontext bist du da gerade?



Sowohl die Rekursionstiefe (was du mit der Zahl der Wiederholungen ansprichst) als auch die Anzahl der Argumente und Variablen die eine Funktion hat tragen zum Stackoverflow bei. Desto mehr Argumente und Variablen eine Funktion übergibt bzw. hat, desto mehr Variablen müssen beim rekursiven Aufruf auf den Stack geschrieben werden.

Im allgemeinen gilt eigentlich für Java das man für Fälle in dennen es zur sehr hohen rekursionstiefen kommen kann lieber Iterative Lösungen wählt. Java ist für sich gesehen nicht für rekursion Optimiert. Sowas findet man eher in funktionalen Programmiersprachen wie Lips und Scheme etc. vor.

Das schon, aber es gibt durchaus Fälle in denen eine Rekursion gegen eine Iteration auszutauschen total bescheuert wäre. Wie bereits gesagt, ist das vom jeweiligen Fall abhängig. Im allgemeinen kann man sagen,dass Rekursion sehr schick sein kann, aber auch sehr schnell eine gewaltige Komplexität erreichen können. Doch sieht man sich beispielsweise die Teile- und Herrsche Algorithmen (Divide &Conquer) an,so ist die Rekursion einen wesentlichen Anteil an wirklich guten Algorithmen hat.
Aber letztlich sollte man ez mal zur Antwort auf die Frage zurückkommen.

Zum einen kann man deutlich sagen ja, sie sind performance lastig...aber dies gilt nicht im allgemeinen. viele sachen sind durch rekursion eleganter zu lösen.

 

[HimBromBeere]

Mit kostspielig meine ich v.a. die Implementierungszeit, da iterative Lösungen meist deutlich mehr Hirnmasse beanspruchen und daher Zeit kosten (welche sich bekanntermaßen in Geld umrechnen lässt, wenn man´s unbedingt will). Und wenn man einen Fertigungszeitpunkt hat, dann zählt in erster Liste erst mal, ob´s funktioniert, sprich die vorhandene Lösung ist erstmal die beste...

Zum einen kann man deutlich sagen ja, sie sind performance lastig...aber dies gilt nicht im allgemeinen. viele sachen sind durch rekursion eleganter zu lösen.

Amen

 

[Antoras]

Erzähl nicht son Käse... Das hat weniger mit der Sprache als mit der Definition der Funktion zu tun.

javac und auch der JIT der JVM können endrekursive Aufrufe nicht optimieren. Es bringt in Java also gar nichts endrekursiv zu programmieren.

 

[faetzminator]

Da gibts im Netz aber auch wiedersprüchliche Informationen, z.B. Programming: Optimierung von Endrekursionen in Java. Ich könnte mir aber durchaus vorstellen, dass es zwar gewisse Optimierungen gibt, dies aber nicht Bereich des Stacks passiert. Dann fliegt das Programm natürlich auch auf die Schnauze...

 

[Gregorrr]

Da gibts im Netz aber auch wiedersprüchliche Informationen, z.B. Programming: Optimierung von Endrekursionen in Java. Ich könnte mir aber durchaus vorstellen, dass es zwar gewisse Optimierungen gibt, dies aber nicht Bereich des Stacks passiert. Dann fliegt das Programm natürlich auch auf die Schnauze...

Naja, wobei man nicht weiß, *was* der da eigentlich gemessen hat... Ohne den Programmcode zu zeigen, kann man alles behaupten...

 

[bERt0r]

Fakt ist, ob endrekursiv oder nicht ist für den Java Stack nicht relevant. Da wird nix wegoptimiert:

public class BlowUp
{
	ArrayList<Integer> list1=new ArrayList<Integer>();
	ArrayList<Integer> list2=new ArrayList<Integer>();
	
	public int blowUp(int i)
	{
		list1.add(i);
		i++;
		return blowUp(i);
	}
	
	public int blowUp2(int i)
	{
		list2.add(i);
		i=blowUp2(i);
		i++;
		return i;
	}
	
	public List<Integer> getList1()
	{
		return list1;
	}
	
	public List<Integer>getList2()
	{
		return list2;
	}
	
	public static void main(String[]args)
	{
		BlowUp blow=new BlowUp();
		try
		{
			blow.blowUp(0);
		}
		catch(StackOverflowError e)
		{
			System.out.println(blow.getList1().size());
		}
		
		try
		{
			blow.blowUp2(0);
		}
		catch(StackOverflowError e)
		{
			System.out.println(blow.getList2().size());
		}
	}
}

Bei mir kommt beide mal ungefähr das gleiche raus.

 

[maki]

Der Java Compiler ist nicht in der Lage Rekursion in Endrekursion zu optimieren, der JIT/Hotspot u.U. schon 😉

Ohne den -server Parameter hat man unter Windows aber nicht viel vom Hotspot Compiler ime.