Rekursion oder Iteration. Was ist schneller?

[mickmack]

Hallo zusammen,

ich habe für mein Programm mehrere doppelt verkettete Listen. Nun möchte ich diese sortieren und stelle mir die Frage, was unter Delphi schneller ist: Ein iterativer oder rekursiver Algorithmus?

Im Netz finde ich dazu ständig widersprüchliche Aussagen, die aber meistens auch von anderen Programmiersprachen ausgehen.

Also ich hätte folgendermaßen argumentiert:
Iterative Lösungen sind schneller, da Rekursionen ihre Zwischenergebnisse auf dem Stack zwischenspeichern und auch von dort wieder lesen müssen.
Bei Iterationen benötigt man nur eine Laufvariable und die Ergebnisvariable, so dass weniger Speicher verbraucht wird.

Wenn nicht lasse ich mich gerne belehren ;-)

[Niels]

Moin!

Es kommt immer ganz drauf an, wie sich das Problem besser lösen lässt. Bei iterativen Problemlösungen kann es sein, dass du viel mehr Hilfsvariablen brauchst. Bei rekursiven kann es passieren, dass sehr viele Rekursionsstufen zu Stande kommen.
Du solltest am besten testen, was in deinem Fall schneller arbeitet. Eine allgemeine Aussage hierzu lässt sich nicht treffen.

MfG Niels

[mickmack]

Danke für die schnelle Antwort.
Die ist praktisch gesehen auch einleuchtend.

Aber würde das theoretisch nicht bedeuten, dass rekursive Lösungen immer schlechter(langsamer) sind, sobald die Rekursionstiefe größer ist als die Anzahl der Hilfsvariablen bei iterativen Lösungen? Und von diesem Fall ist doch meistens, besonders bei dynamischen Listen, auszugehen.

Was spricht dann noch für Rekursion?
1. übersichtlicher
2. teilweise leichter beweisbar
3. was noch?

Und stimmt meine Begründung?

Zitat:

Iterative Lösungen sind schneller, da Rekursionen ihre Zwischenergebnisse auf dem Stack zwischenspeichern und auch von dort wieder lesen müssen.
Bei Iterationen benötigt man nur eine Laufvariable und die Ergebnisvariable, so dass weniger Speicher verbraucht wird.

[negaH]

Zitat:

Was spricht dann noch für Rekursion?
1. übersichtlicher
2. teilweise leichter beweisbar
3. was noch?

4. viel weniger Buganfällig

Rekursive Funktionen sind in der Regel immer viel einfacher aufgebaut, besonders bei Tries. Allerdings habe ich auch schon rekursive Lösungen für rein iterative Probleme gesehen, und die waren natürlich viel ineffizienter.

Iterative Lösungen sind meistens wesentlich effizienter und leichter zu kontrolieren, dh. der Programfluß kann zb. besser abgebrochen werden usw.

Die eigentliche Frage muß nicht lauten "ist iterativ besser oder schlechter als rekursiv", sondern eher "um wieviel ist eine iterative Lösung komplizerter aber schneller als eine rekursive Lösung".

Meistens ist es so das ein umschreiben einer bestehenden rekursiven Procedure in eine iterative viel mehr Grips und Zeit kostest als das was sie letzendlich an Performancesteigerung bringt. Auf heutigen Systemen muß man schon enorm tiefe Tries haben um an Grenzen in den rekursiven Proceduren zu kommen.

Gruß Hagen

[Chewie]

Es gibt auch Algorithmen, bei denen rekursive Algorithmen sehr schnell an ihre Grenzen stoßen, wie z.B. Fibonacci. Die iterative Variante ist hier wesentlich performanter und speicherschonender.