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.
Ich tendiere zu nein. Sollte ich die Zeit dafür finden, ließe sich evt. ein Beweis für die
Äquivalenz beider Verfahren finden.
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.
Ein klares Zeichen, dass du Beiträge entweder nicht liest oder nicht verstehst. Es ist bereits gezeigt worden, dass die iterative Lösung der rekursiven
nicht überlegen ist. Tail
recursion is recursion! Bitte lese zukünftig Beiträge, bevor du ihnen widersprichst.
greetz
Mike