Rekursion vs. Iteration

[Delphi-Laie]

Zitat von alzaimar:

Ich kann mit Aussagen, wie "Rekursion ist per se langsamer als Iteration" nichts anfangen. Denn es ist Quatsch.

Natürlich. So pauschal eine solche Aussage ist, so falsch ist sie auch.

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. 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.