Rekursion grundsätzlich langsamer?

Guten Tag,
ich gehe eine Baumstruktur mit bis zu 32 Ebenen rekursiv durch. Jetzt frage ich mich, ob Rekursion denn grundsätzlich langsamer ist, als wenn ich alles "ausschreiben" würde?
Beste Grüße,
Daniel

Hallo bloody_fighter,

nein, Rekursion ist nicht grundsätzlich langsamer(*). Vor allem ist Rekursion die beste Vorgehensweise, um Baumstrukturen zu durchlaufen. Verständlichkeit und Klarkeit des Code ist weit wichtiger als die Hatz nach Mikrosekunden Laufzeitverbesserung. Bei solchen Fragen solltest du dir immer vor Augen halten: "premature optimization is the root of all evil".

Siehe auch Gibt es Rekursionen die sich nicht in eine Iteration umwandeln lassen?

herbivore

(*) von den angesprochenden und nicht spürbaren Mikrosekunden in die eine oder anderen Richtung mal abgesehen.

Wie würdest du eine Baumstruktur "ausschreiben"?
Rekursion würd ich sowieso nicht als grundsätzlich langsamer ansehen. Von etwas "weiter oben" betrachtet gehst du so oder so über alle Elemente, egal wie du die raussuchst.

Ja so viel ich weiß verbraucht Rekursion ja mehr Arbeitsspeicher im Stack, deswegen dachte ich mir, dass es vielleicht auch langsamer sein könnte. Ja das Problem, das ich habe, handelt um eine AlphaBeta Suche im Skat..und das ganze ist doch sehr zeitintensiv, letztendlich wird mir wohl nichts übrig bleiben als auf C / C++ umzusteigen...
Ausschreiben würde ich es so, dass ich die Funktion quasi in sich selber hardgecodet reinschreiben würe, was natürlich extrem unschön wäre.

Hallo,

mit dem erhöhten Speicherverbrauch durch die Stacks jedes Funktionsaufrufs hast du recht, trotzdem führt beim Bäume durchlaufen kaum nen Weg an rekursiven Lösungen vorbei da iterative Lösungen zwar immer möglich sind, aber bei komplexen Bäumen extrem komplex werden können und im schlimmsten Fall arbeitet man selber noch mit stackartigen Datenstrukturen um das hinzukriegen und dann hat man erst recht nichts gewonnen.

Wieso du die Sprache wechseln willst, ist mir aber schleierhaft. Was für Vorteile erwartest du denn? C# ist da genauso schnell wie C++ und bei dem Problem kommts ja eh auf optimale Datenstrukturen an - das kann man in egal welcher Sprache besser oder schlechter lösen.

Ja, Rekursion ist technisch langsamer. Nicht nur, weils mehr Speicher auf dem Stack verbraucht, sondern vor allem wegen der Funktionsaufrufe.
Ob das ins Gewicht fällt, kommt auf deine Funktion an. Wenn du die Fakultät rekursiv ausrechnen möchtest, wirds deutlich langsamer sein, weil dein Funktionsrumpf fast schon weniger rechenaufwändig ist, als der Funktionsaufruf an sich.
Du solltest aber vor allem bedenken, dass es meist nicht ausschlaggebend ist. Die beiden wichtigsten Punkte hat herbivoir ja schon geäußert. Rekursion ist die bevorzugte Methode, um Baumstrukturen zu durchlaufe, und premature optimization ist the root of all evil.
Bei deiner Alpha/Beta Suche solltest du erstmal abschätzen, was das alles bringt. Wenn du zu dem Ergebnis kommst, dass du durch weglassen der Rekursion 10% sparst, dann lohnt sich das nicht. Und überhapt musst du schauen, ob sich Optimierung in irgendeiner Weise lohnt. Ob dein Programm 10ms oder 10% schneller läuft, ist egal. Ob dein Programm unendlich lang läuft, oder 10% schneller, ist auch egal 😉

Hallo bloody_fighter,

AlphaBeta-Suche ist wegen der Masse an zu prüfenden Kombinationen langsam, nicht wegen der Rekursion. Wenn du AlphaBeta beschleunigen willst, ist es natürlich nicht unwichtig, eine gute und schnelle Datenstruktur für die Repräsentation der Zustände zu haben, aber noch viel, viel, viel wichtiger ist es jedoch, die Anzahl der Kombination, die untersucht werden müssen, zu reduzieren. Entweder im in dem man sie früh als so schlecht erkennt, dass man sie nicht weiter untersuchen muss, aber auch, in dem man Symmetrien erkennt. Wenn erst A und dann B ausgespielt oder erst B und dann A, kann es sein, dass in beiden Fällen der gleiche Zustand erreicht wird. Bei nativer AlphaBeta-Suche würde dann der Zustand zwei mal untersucht werden, einmal im A-B-Zweig und einmal im B-A-Zweig. Sowas gilt es zu erkennen und zu vermeiden.

Aber mich deucht, wir hätten das alles schonmal besprochen.

herbivore

Aber mich deucht, wir hätten das alles schonmal besprochen.

Genau. Und zwar hier: Alpha-Beta Algorithmus: Wie groß ist der Overhead durch Objektorientierung?