Rekursion vs. Iteration

[negaH]

Zitat:

Meine rekursive Implementierung der Fibonacci-Folge berechnet auch jeden Wert nur einmal. Ich gehe mal davon aus, dass du dich mit Rekursion und funktionaler Programmierung kaum außeinandergesetzt hast, da man schon in den Anfängen über die Konzepte des Tuplings stößt - was zur rekursiven Implementierung von Fibonacci in O(n) führt.

Wenn eine rekursive Variante eine Algos. 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".

Also ganz unabhängig von "funktionaler Programmierung" und "Tupeling".

Gruß Hagen