Mich würde in diesem Zusammenhang allerdings einmal interessieren, ob bei Problemlösungen, die sowohl iterativ als auch rekursiv möglich sind, es auch Fälle gibt, in denen die Rekursion hinsichtlich des Laufzeitverhaltens der Iteration substantiell (also vom Komplexitätsverhalten her) überlegen ist.
Ist unmöglich, da das Komplexitätsverhalten vom Algorithmus (also der Art der Problemlösung) und nicht von der Implementierung des Algorithmus (rekursiv/iterativ) abhängt. Du meinst schon das mit der Groß-O-Notation, oder? Denn ein rekursiver Quicksort und ein iterativer Quicksort haben beide eine Laufzeit von n*log(n) im Schnitt.
Zitat:
Nachzuweisen, daß eine iterative einer (bestimmten) rekursiven Lösung überlegen ist, bedurfte es ja nur einer Folge, die schon seit dem späten Hochmittelalter (oder frühen Spätmittelalter) bekannt ist.
Das "nachzuweisen" ist trivial.
Als Gegenbeispiel führe ich mal die Türme von Hanoi an:
http://de.wikipedia.org/wiki/Türme_v...er_Algorithmus
Die rekursive Implementierung ist deutlich besser verständlich als die iterative. Beide haben natürlich das gleiche exponentielle Laufzeitverhalten.
Noch ein bereits genanntes Gegenbeispiel: Rekursiver Quicksort vs. iterativer Bubblesort. Sind ja beides Lösungen für das Sortierproblem - aber die rekursive Implementierung der Lösung ist deutlich schneller im Average Case
