Rekursion vs. Iteration

[JasonDX]

Zitat von Delphi-Laie:

Außerdem wurde mit der rekursiven Berechnung irgendeines Gliedes der Fibonacci-Folge diese pauschale Lobhudelei der Rekursion bereits widerlegt, denn dort wird jeder Zwischenwert doppelt, dreimal oder noch (viel) häufiger berechnet.

Um Hagens Worte konkreter zu formulieren: 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.

Zitat von negaH:

Es gäbe da ein "Argument" pro Iterativ:
Nämlich das es bestimmte Problemstellung gibt die man nicht rekusiv formulieren kann.

Es könnte schwierig werden, solche Problemstellungen zu finden. Lambda-Ausdrücke sind gleichmächtig wie TMs, somit kann alles, was iterativ berechenbar ist, auch rekursiv beschrieben werden.

greetz
Mike