Rekursion oder Iteration. Was ist schneller?

[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