Rekursion vs. Iteration

[gammatester]

Zitat von JasonDX:

(Schonmal versucht zu beweisen, dass deine Schleife wirklich die Fibonacci-Reihe berechnet? ^^). Eine rekursive Beschreibung rekursiv implementieren bringt dann deutlich weniger Probleme und Fehlerpotential mit sich, als den rekursiv beschriebenen Algorithmus iterativ zu implementieren.

Na Logo, und bei der Gelegenheit kommt man auch sofort auf den viel besseren Algorithmus: [F_{n+1}, F_n] = [[1 1], [1 0]] * [F_n, F_{n-1}]. Es läuft also darauf hinaus, die Potenzen der Matrix A = [[1 1], [1 0]] zu berechnen. Die einfache Iteration berechnet A^n via n-facher Multiplikation und ist O(n), der verbesserte Algo berechnen A^n nach dem binären "Quadriere-und-Multipliziere"-Algorithmus und ist O(log(n)).

[JasonDX]

Zitat von Delphi-Laie:

Zitat von JasonDX:

Zitat von Delphi-Laie:

Zitat von negaH:

Erstens dient ja die Formel als Basis und wenn man 1 zu 1 diese als Implementierung in SW wieder findet so erhöht das enorm die Verständlichkeit. Zweitens sind rekursive Formeln/Algos meistens einfacher verständlich.

Naja, auf Anhieb habe ich nur die Fakultät und die Fiboncci-Folge als Paradebeispiele. Sicher erklärt die (nichtiterative) Formel bei letzterem nicht das Wesen jener Folge, aber sie ist als solche deshalb nicht weniger verständlich.

In deinem letzten Satz sollte dir der Widerspruch deiner Aussage auffallen. "Man versteht nicht das Wesen der Folge, aber der Code ist nicht weniger verständlich". Der Code ist vllt. nicht weniger lesbar, aber seine Aufgabe ist deutlich unverständlicher.

Wo ist ein/der Widerspruch?

Die rekursive Definition der Fibonacci-Folge ist trivial, und ihr Verlauf ist auf den ersten Blick halbwegs abschätzbar - im Gegensatz zur iterativen Implementierung; Dort ist eine Einschätzung der Funktion verhältnismäßig komplex.

Zitat von Delphi-Laie:

Ohne Rekursion - sogar ohne Iteration - kann man die Glieder der Fibonacci-Folge über Berechnungen mit der (Quadrat-)Wurzel aus 5 ermitteln. Diese Formel ist leicht zu implementieren bzw. aus dem Quellcode (nur wenige Anweisungen, deshalb leicht zu erfassen) leicht die Formel abzuleiten.

Ja, sie ist leicht implementierbar und hat (rein theoretisch) konstante Laufzeit - aber ein grobes Genauigkeitsproblem.

Zitat von gammatester:

Zitat von JasonDX:

(Schonmal versucht zu beweisen, dass deine Schleife wirklich die Fibonacci-Reihe berechnet? ^^). Eine rekursive Beschreibung rekursiv implementieren bringt dann deutlich weniger Probleme und Fehlerpotential mit sich, als den rekursiv beschriebenen Algorithmus iterativ zu implementieren.

Na Logo, und bei der Gelegenheit kommt man auch sofort auf den viel besseren Algorithmus: [F_{n+1}, F_n] = [[1 1], [1 0]] * [F_n, F_{n-1}]. Es läuft also darauf hinaus, die Potenzen der Matrix A = [[1 1], [1 0]] zu berechnen. Die einfache Iteration berechnet A^n via n-facher Multiplikation und ist O(n), der verbesserte Algo berechnen A^n nach dem binären "Quadriere-und-Multipliziere"-Algorithmus und ist O(log(n)).

Womit man dann zurück zum Punkt kommt, obs schöner/besser/toller/* ist den optimierten Algorithmus iterativ oder rekursiv zu implementieren
Mein Beitrag war auf die iterative Schleife bezogen. Diese bringt keine Laufzeitverbesserung, ist dafür aber weniger intuitiv und damit schlechter erkennbar, von Fehlerquellen mal ganz abgesehn

greetz
Mike

[negaH]

Die Eingangsfrage ist ob rekusive oder iterative Umsetzungen eines Algos besser oder schlechter ist.

Man kann nun Äpfel mit Birnen vergleichen oder unsachlich argumentieren (zb. was hat Assembler damit zu tuen, oder was hat die Implementierung von Windows damit zu tuen, oder welche Relevanz hat eine Diskussion wenn man zb. für Fibonacci einen komplett anderen Algorithmus als Lösung vorschlägt und das als Basis für eine Begründung wählt um die iterative Methode zu untermaueren ?)

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.

Wer sich mit programmierbarer Hardware, also FPGAs auskennt weiß das man dort zb. mit den Sprachen VHDL, Verilog oder Abel sehr wohl ein Problem iterativ wie auch rekursiv beschreiben kann. Die nachfolgende Synthese wird in beiden Fällen das exakt gleiche Resultat erzeugen.

Die Unterscheide zwischen beiden sind also begründet in der Architektur der Hardware und nicht im Theoretischen. Auf zb. FPGAs verhalten sich beide gleich, benötigen identische Resourcen und sind identisch performant. Auf ASICs ändert sich dieses Verhältnis, aber je umfangreicher die Berechnungen werden desto mariginaler wird dieser Unterschied.

Ergo: man kann das iA. vernachlässigen und die Prioritäten anders legen. Nämlich auf Verständlichkeit und damit Wartbarkeit. Das Ändern des Algos., zb. ersetzen durch einen besseren, wird in fast allen Fällen bessere Resultate erzielen als sich auf diese mariginalen Unterschiede zu stürzen.

@Gammatester:

dein Vergleich hinkt: du vergleichst zwei unterschiedliche Lösungswege miteinander und schließt daraus das die iterative Version von Vorteil wäre.

Gruß Hagen

PS: übrigens berichte ich hier aus meinem 25jährigen Erfahrungsschatz und vertrete hier nur eine Meinung. Wer mich kennt weiß das ich der Letzte bin der nicht aus jedem Stück HW das letzte an Peformance rauszuholen versucht, und dh. eben auch das man einen Vergleich zwischen beiden Implementierungsmöglichkeiten praktisch durchführt.

[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.

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.

[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?!

[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

[negaH]

Zitat:

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.

vorsicht, jetzt begibts du dich auf Glatteis. Es gibt einen mathematischen Beweis das es solche Probleme geben muß. Leider finde ich jetzt nicht auf die Schnelle bei Wikipedia die richtige Seite.

Solche Probleme gibt es also wirklich. War irgenwas mit einer Ameisensimulation oä.

Gruß Hagen