rekursionen vorteilhaft???
-
wo wendetet man eigentlich in der ernsthaften programmierung von allgemeiner software rekursionen an? mein info-lehrer legt immer viel wert auf rekursionen, weil sie eleganter und leichter zu warten sind. allerdings meint er auch dass sie langsamer als iterative algorithmen sind.
wo wendett man denn wirklich noch rekursionen an, die sich auch vorteilhaft auswirken?
-
Bei vielen Divide&Conquer-Algorithmen. Quicksort wird zB auch nur selten iterativ hingeschrieben.
-
Rekursion ist vor allem beim Entwurf von Algorithmen sehr hilfreich. Ob ne wirklich gute Implementierung im Endeffekt rekursiv ist oder nicht, ist ne ganz andere Frage.
-
Iterative Verfahren machen Sinn, wenn man das maximum an Performance aus einem Algorithmus rauskitzeln möchte. Die Kosten von Funktionsaufrufen sind aber architekturabhängig, weshalb man das nicht verallgemeinern kann. Die Performance von rekursiven Aufrufen mit Parametern ist z. B. bei der x86-64 Architektur erheblich performanter als bei der x86, da nicht der Stack zur Parameterübergabe genutzt werden muss. Man könnte also viele rek. Algorithmen genauso effizient schreiben wie iterative Algorithmen(mind. in Assembler).
-
Ausserdem ist praktisch jeder Compiler in der Lage, Tail-Rekursionen in ein iteratives Konstrukt umzuwandeln.
-
M.Sc. schrieb:
Die Performance von rekursiven Aufrufen mit Parametern ist z. B. bei der x86-64 Architektur erheblich performanter als bei der x86, da nicht der Stack zur Parameterübergabe genutzt werden muss.
Das verstehe ich nicht. Die Parameter müssen doch auf den Stack, sonst überschreibe ich doch beim nächsten Aufruf die alten Parameter.
-
Jester schrieb:
M.Sc. schrieb:
Die Performance von rekursiven Aufrufen mit Parametern ist z. B. bei der x86-64 Architektur erheblich performanter als bei der x86, da nicht der Stack zur Parameterübergabe genutzt werden muss.
Das verstehe ich nicht. Die Parameter müssen doch auf den Stack, sonst überschreibe ich doch beim nächsten Aufruf die alten Parameter.
Uups, hast natürlich recht! Ich habe gerade nur an die Kosten von Funktionsaufrufen gedacht, ohne weiter zu denken. Das Wochenende kommt zum Glück endlich!
-
nein, es muss nicht immer ein aufruf mit stackpush vorhanden sein. bsp:
int CFoo::Bar(int value) { if(m_Index<value) return m_pLeft->Bar(value); return m_pRight->Bar(value); }natürlich ist das hier kein terminierender aufruf, soll nur beispiel sein ;).
bei diesem beispiel wird der compiler statt einem call mit stackpush usw. nur den aktuellen this pointer durch den von left bzw right ersetzen und einen jmp an den anfang der funktion machen.
das kann der compiler wenn der zu übergebende parameter mit dem der der funktion übergeben wurde identisch ist und meist hilft man wenn man return aufruft, selbst wenn der return value void sein sollte.und ja, das kann man gut verwenden, in komplexeren fällen kann rekursiver aufruf schneller sein als iteratives abarbeiten (man spart ein paar memmoves durch compileroptimierungen).
-
Doktor Prokt schrieb:
Ausserdem ist praktisch jeder Compiler in der Lage, Tail-Rekursionen in ein iteratives Konstrukt umzuwandeln.
Das mag vielleicht für Programmiersprachen gelten die kein Konstrukt für Schleifen anbieten, bei einem handelsüblichen C++ Compiler habe ich das aber noch nicht beobachten können.
-
Optimizer schrieb:
Doktor Prokt schrieb:
Ausserdem ist praktisch jeder Compiler in der Lage, Tail-Rekursionen in ein iteratives Konstrukt umzuwandeln.
Das mag vielleicht für Programmiersprachen gelten die kein Konstrukt für Schleifen anbieten, bei einem handelsüblichen C++ Compiler habe ich das aber noch nicht beobachten können.
In Common Lisp sind Tailrekursionen sehr ueblich, obwohl die Sprache wahrscheinlich mehr Schleifenkonstrukte als jede andere Sprache anbietet.
Der GCC kann uebirgens auch Tailrekursionen eliminieren.