rekursiv vs iterativ
-
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.
