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?
Ja.
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.
Ich meinte doch ausdrücklich, ob es eine
schnellere rekursive Lösung gibt. Die Verständlichkeit ist unberührt.
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
Der Vergleich hinkt m.E. etwas. Es lassen sich zum einen auch rekursive (und auch iterative) Algorithmen finden, die langsamer als Bubblesort sind (Trippelsort, Slowsort), zum anderen gibt es auch iterative Sortieralgorithmen, die von der Geschwindigkeit her dem Quicksort wahrscheinlich mindestens ebenbürtig sind.