Rekursion vs. Iteration

[negaH]

Zitat von Delphi-Laie:

Zitat von negaH:

Der einzige Grund warum eine rekursive Lösung unter Umständen einen leichten Performance-/Speicheroverhead hat liegt
in der Rechnerarchitektur begründet, ansonsten wird es zwischen beiden keinen Unterschied geben.

Ganz bestimmt nicht. Die Komplexität bzw. Effizienz von Algorithmen hat zunächst einmal überhaupt nichts mit ihrer Umsetzung zu tun.

Korrekt, du verstehst langsam. Aus dieser Sichweise heraus kann man also den Algo. iterativ wie auch rekursiv aufbauen (wenn es eine rekursive Version dafür gibt) ohne das es einen Untrschied in desen Komplexität gibt.

Erst wenn man anfängt diesen Algo. zu implementieren auf einer jeweiligen Hardware wird es nur und ausschließlich nur auf Grund dieser Hardware leichte Unterschiede zu Gunsten der iterativen Lösung geben.

Damit untermauert deine Aussage ja meine

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.

Eben nicht. Wo ist da ein Beweis ? wenn man Äpfel mit Birnen vergleicht. Ich warte schon auf dein Argument das ja Windows auf Grund dessen das man dort alles rekursiv gelöst hat immer schlechter wird und jedes denkbare HW-System massiv ausbremst. Kannst du mir sagen woher du eigentlich weißt das die Entwickler bei MS rekursive statt iterative Implementierungen bevorzugen ?

Ich setze dagegen und behaupte das ich Fibonacci zb. auf einem FPGA sowohl iterativ wie rekursiv implementieren könnte und am Ende beides absolut identisch sein muß ! Und dabei bin ich sogar noch so fair und benutze in beiden Fällen als algortihmische Basis auch den gleichen Algorithmus und nicht Äpfel und Birnen, nicht ASIC vs. FPGA usw.

Gruß Hagen

[negaH]

Zitat:

bei dem die Rekursion hinsichtlich Komplexität die überlegene Lösung darstellt. Ich bin gespannt darauf.

Na endlich kommen wir weiter. Es gibt keinen Überlegenen, iterativ vs. rekursiv sind identisch und erst die Fähigkeiten der Hardware macht einen Unterschied. Aber dieser ist eben oft nur marginal im Speicher wie Performancebereich, ansonsten bleibt die Komplexität des Algos. erhalten, egal ob rekursiv/iterativ. Alle weiteren Tricks lassen sich dann rekursiv wie auch iterativ anwenden da es Tricks zur Verbesserung der Komplexität des Algos. sind.

Aber in der Verständlichkeit, Wartbarkeit, Definierbarkeit eines Bweweise für dessen Korrektheit gibt es gewaltige Unterschiede.

Gruß Hagen

[negaH]

Es gäbe da ein "Argument" pro Iterativ:

Nämlich das es bestimmte Problemstellung gibt die man nicht rekusiv formulieren kann. Aber das ist am Thema vorbei, da wir davon ausgehen können das ein Vergleich rekursiv vs. iterativ nur dann Sinn macht wenn auch auch vom Problem her beide Möglichkeiten gibt.

Gruß Hagen

[Delphi-Laie]

Zitat von negaH:

Zitat von Delphi-Laie:

Zitat von negaH:

Der einzige Grund warum eine rekursive Lösung unter Umständen einen leichten Performance-/Speicheroverhead hat liegt
in der Rechnerarchitektur begründet, ansonsten wird es zwischen beiden keinen Unterschied geben.

Ganz bestimmt nicht. Die Komplexität bzw. Effizienz von Algorithmen hat zunächst einmal überhaupt nichts mit ihrer Umsetzung zu tun.

Korrekt, du verstehst langsam. Aus dieser Sichweise heraus kann man also den Algo. iterativ wie auch rekursiv aufbauen (wenn es eine rekursive Version dafür gibt) ohne das es einen Untrschied in desen Komplexität gibt.

Erst wenn man anfängt diesen Algo. zu implementieren auf einer jeweiligen Hardware wird es nur und ausschließlich nur auf Grund dieser Hardware leichte Unterschiede zu Gunsten der iterativen Lösung geben.

Damit untermauert deine Aussage ja meine

Wenn einer 'was nicht sehen will.... Letzlich wiederholtest Du nur Deine Aussage und besitzt sogar noch die Stirn zu behaupten, ich hätte Deine Aussage untermauert, bleibst den Nachweis dieser abenteuerlichen Behauptung jedoch schuldig. Wenn iterativ und rekursiv wirklich nie einen Unterschied ausmachen, dann kann es an der Hardware ja erst recht kaum liegen.

Zitat von negaH:

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.

Eben nicht. Wo ist da ein Beweis ? wenn man Äpfel mit Birnen vergleicht. Ich warte schon auf dein Argument das ja Windows auf Grund dessen das man dort alles rekursiv gelöst hat immer schlechter wird und jedes denkbare HW-System massiv ausbremst.

Diese abgedroschene Floskel, rhetorisch jedoch leere Phrase mit den Äpfeln und den Birnen. Man kann alles und jeden miteinander vergleichen. Wenn man Äpfel mit Birnen vergleicht, was wird man wohl feststellen? Gemeinsamkeiten und Unterschiede!

Allein, daß die Rekursion bei Fibonacci wiederholt (!) Zwischenwerte generiert, was die iterative Variante eben nicht tut, macht sie mir suspekt. Du warst es, der Rekursion vs. Iteration im wesentlichen auf Hardware reduziertest. Nun, dann frage ich mich, warum Windows trotz immer schnellerer Computer weiterhin dauerlahmt.

Zitat von negaH:

Kannst du mir sagen woher du eigentlich weißt das die Entwickler bei MS rekursive statt iterative Implementierungen bevorzugen ?

Sicher nicht, weil Du mir etwas in den Mund zu legen beabsichtigst. Du darfst gern den Versuch antreten, mir nachzuweisen, daß ich das irgendwo behauptet hätte.

Zitat von negaH:

Ich setze dagegen und behaupte das ich Fibonacci zb. auf einem FPGA sowohl iterativ wie rekursiv implementieren könnte und am Ende beides absolut identisch sein muß !

Nun, das kann ich Dir nicht widerlegen, noch kann ich meine Ansicht beweisen. Ich kann nur ein (kleines) Testprogramm schreiben (was ich bereits tue) und dann messen. Vielleicht kannst Du ja Deine Behauptung beweisen?!