rekursiv vs iterativ
-
hustbaer schrieb:
üblicherweise ist das die rekursive variante, da einem der compiler/die CPU viel arbeit abnimmt, und das besser, als man es selbst machen würde.
Da müsste der Compiler ja die ganzen rekursiven Funktionsaufrufe wegoptimieren, da diese ja einen gewissen Overhead produzieren. Ist das tatsächlich der Fall?
-
siecpp schrieb:
hustbaer schrieb:
üblicherweise ist das die rekursive variante, da einem der compiler/die CPU viel arbeit abnimmt, und das besser, als man es selbst machen würde.
Da müsste der Compiler ja die ganzen rekursiven Funktionsaufrufe wegoptimieren, da diese ja einen gewissen Overhead produzieren. Ist das tatsächlich der Fall?
Nein, das ist nicht der Fall, Compiler können Rekursionen nur sehr bedingt optimieren, nämlich eigentlich nur sog. "Tail Recursion". Also Rekursive Aufrufe ala "return myself(param);". Wenn du etwas wie z.B. QuickSort implementierst, kommst du mit Tail Recursion nicht aus, und der Compiler wird keine Chance haben, sämtliche rekursiven Aufrufe wegzuoptimieren.
Aber wieso gehst du davon aus, dass ein rekursiver Funktionsaufruf Overhead wäre? Oder besser: mehr Overhead, als eine selbst gewurstelte iterative Implementierung hätte.
Eine iterative Implementierung ist ja nicht einfach die Rekursive minus den rekursiven Aufrufen. Statt den rekursiven Aufrufen musst du ja eigenen Code schreiben, der dann diverse Dinge auf selbst gemanagten Stacks speichert etc.Aber du kannst es ja einfach mal ausprobieren, und uns dann deine Ergebnisse mitteilen.
-
unskilled schrieb:
SeppJ schrieb:
Nexus schrieb:
unskilled schrieb:
Sehr schönes aktuelles Beispiel:
Warcraft 3
Dort wird das abgehen der Wegpunkte rekursiv berechnet - da bekommt man es auch hin, den Stack zum Überlaufen zu bekommenWürde ich gern mal ausprobieren, kannst du etwas konkreter werden?
Ich dachte da kommt vorher immer ein Meldung die sagt, dass die Wegepunkteliste voll sei.
Ne, da kommt eine Zugriffsverletzung und dein WC3 schmiert ab - der andere freut sich, weil er nen Hack hat, der das nicht nur halb automatisch für ihn erledigt sondern auch noch so im Programmspeicher rumpfuscht, dass er selbst keine Probleme hat...
--------------------------------------------------------------------------
WARCRAFT III: THE FROZEN THRONE VERSION HISTORY
----------------------------------------------------------------------------------------------------------------------------------------------------
Patch 1.24d
--------------------------------------------------------------------------FIXES
- Fixed a client crash related to queuing too many invalid build commands
("crash hack").============================
-
VS 2008 optimiert die Tail Recursion meiner Fakultät nicht weg. Die Fibanocci-Folge zu bestimmen dürfte iterativ auch performanter sein. Schöner nicht.
-
Badestrand_ schrieb:
VS 2008 optimiert die Tail Recursion meiner Fakultät nicht weg.
hast du das im release probiert? hast du dir den assembler-code angesehen?
Die Fibanocci-Folge zu bestimmen dürfte iterativ auch performanter sein. Schöner nicht.
vermutlich, ja. und natürlich sind alle anderen dinge auch so einfach iterativ zu implementieren wie die fibanocci folge.
-
hustbaer schrieb:
Badestrand_ schrieb:
VS 2008 optimiert die Tail Recursion meiner Fakultät nicht weg.
hast du das im release probiert? hast du dir den assembler-code angesehen?
Ja, und es hat mich auch gewundert.
hustbaer schrieb:
Die Fibanocci-Folge zu bestimmen dürfte iterativ auch performanter sein. Schöner nicht.
vermutlich, ja. und natürlich sind alle anderen dinge auch so einfach iterativ zu implementieren wie die fibanocci folge.
Danach sollte mein Post eigentlich nicht klingen
-
hustbaer schrieb:
Aber wieso gehst du davon aus, dass ein rekursiver Funktionsaufruf Overhead wäre? Oder besser: mehr Overhead, als eine selbst gewurstelte iterative Implementierung hätte.
Eine iterative Implementierung ist ja nicht einfach die Rekursive minus den rekursiven Aufrufen. Statt den rekursiven Aufrufen musst du ja eigenen Code schreiben, der dann diverse Dinge auf selbst gemanagten Stacks speichert etc.Natürlich braucht man bei iterativen Implementierungen zusätzlichen Code. Ein Funktionsaufruf hat aber dennoch meistens Kosten, die ich bei einer iterativen Implementierung vermeiden kann. Wie "teuer" ein Funktionsaufruf ist, hängt natürlich stark von der verwendetet Architektur ab. Bei x86 sind Fuktionsaufrufe leider relativ langsam. Ich muss Register sichern, Argumente über den Stack austauschen, Rücksprungadresse sichern Registerinhalte wiederherstellen etc. Das brauche ich alles bei der iterativen Implementierungen nicht in dieser Weise.
hustbaer schrieb:
Aber du kannst es ja einfach mal ausprobieren, und uns dann deine Ergebnisse mitteilen.
Das wäre natürlich das Beste. Vielleicht finde ich am Wochenende Zeit das zu tuen.
-
siecpp schrieb:
hustbaer schrieb:
Aber du kannst es ja einfach mal ausprobieren, und uns dann deine Ergebnisse mitteilen.
Das wäre natürlich das Beste. Vielleicht finde ich am Wochenende Zeit das zu tuen.
Implementiere doch mal Tiefensuche (http://de.wikipedia.org/wiki/Tiefensuche) rekursiv und iterativ, wobei jeweils auch die "Discovery- und Finishing-Times" berechnet werden (siehe "Algorithmusbeispiel: Erzeugen des Tiefensuchwaldes (rekursiv)" Abschnitt bei Wikipedia).
Prinzipiell lohnt sich da nämlich die Umwandlung rekursiv->iterativ, da die Anzahl der rekursiven Aufrufe linear mit der Größe des Graphen ansteigen kann. Andererseits braucht man bei der iterativen Variante einen expliziten Stack, so dass der Vergleich fair bleibt. Außerdem sieht man durch die Berechnung der Discovery- und Finishing-Times, dass es durchaus kompliziert werden kann einen rekursiven Algorithmus in einen iterativen Algorithmus umzuformen (selbst mit expliziten Stack).
-
hustbaer schrieb:
vermutlich, ja. und natürlich sind alle anderen dinge auch so einfach iterativ zu implementieren wie die fibanocci folge.
Das glaube ich nicht. Gehent tut es afaik immer, aber das es immer einfach ist bezweifle ich sehr stark. (aber ich nehme mal an, dass du das ironisch gemeint hast?)
-
Meine Faustregel: Wenn etwas ironisch gemeint sein könnte, ist es das auch.
-
Bashar schrieb:
Meine Faustregel: Wenn etwas ironisch gemeint sein könnte, ist es das auch.
Dann kannst du aber kein Wort mehr von volkard ernst nehmen. :p(btw: der hat sich auch schon lange nicht mehr blicken lassen..)
-
Ja, richtig: es war nicht ernst gemeint.
