Rekursion vs. Iteration

[JasonDX]

Zitat von negaH:

Werte mehrfach berechnet im Vergleich zur iterative Variante dann existiert ein Unterschied in der Komplexität beider Implementierungen. Ein Unterschied in der Komplexität bedeutet das es unterscheidliche nicht mehr vergleichbare Algorithmen sind. Ergo: Äpfel und Birnen und damit nichts aussagend für den Vergleich "rekursiv vs. iteratv".

Ja, deshalb habe ich auch den Apfel auf eine Birne abgebildet - nämlich aus der stupiden rekursiven Implementierung, bei der Werte mehrfach berechnet werden, eine Variante, bei der jeder Wert nur einmal berechnet wird. Dieser Algorithmus hat dann rekursiv implementiert die selbe Laufzeit wie DLs iterative Schleife. Ich wollte damit seiner Behauptung, die iterative Implementierung sei besser als die rekursive, begründet widersprechen. Tupling habe ich erwähnt, weil das ein Prinzip ist, mit dem rekursive Funktionen relativ einfach optimiert werden können; Eben bspw. um nicht Werte mehrfach zu berechnen, oder auch um eine endrekursive (keine Ahnung wie das auf Deutsch heißt, tailrecursive jedenfalls ) Berechnung zu bauen.

greetz
Mike