Rekursion vs. Iteration

[Delphi-Laie]

Zitat:

Zitat von JasonDX (Beitrag 1027935)

Zitat:

Zitat von Delphi-Laie (Beitrag 1027841)

Zitat:

Zitat von negaH (Beitrag 1027836)

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?

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. Doch wie man aus dieser Gleichung die rekursive Berechnung der Fibonaccifolgenglieder ermitteln soll, erschließt sich mir nicht, und ob es überhaupt möglich ist, können nur Mathematiker beantworten.

[MrSpock]

Ich denke, dass auch die meisten backtracking Probleme am besten über Rekursion gelöst werden.

z.B.: Damenproblem, Springerproblem, Wegesuche im Labyrinth

[gammatester]

Zitat:

Zitat von JasonDX (Beitrag 1027935)

(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:

Zitat von Delphi-Laie (Beitrag 1027946)

Zitat:

Zitat von JasonDX (Beitrag 1027935)

Zitat:

Zitat von Delphi-Laie (Beitrag 1027841)

Zitat:

Zitat von negaH (Beitrag 1027836)

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:

Zitat von Delphi-Laie (Beitrag 1027946)

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:

Zitat von gammatester (Beitrag 1027949)

Zitat:

Zitat von JasonDX (Beitrag 1027935)

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

[negaH]

Zitat:

Ein weiterer Vorteil von rekursiven Implementierungen ist die Korrektheit.

Korrekt. Man wird dann nämlich sehr oft den Beweis für die Korrektheit ebenfalls rekursiv formulieren können und das ist wesentlich einfacher. Um Fehldeutungen dieses Satzes von vornherein auszuschließen. Ich beziehe mich auf den Beweis der Korrektheit des angewendeten Algorithmus auf höherer Ebene. Also nicht ob das Program am Ende tut was man geplant hat, also den Einzelfall sondern den Beweis das das Program in jedem Falle das tuen wird was man geplant hat. Sowas erschlägt man nicht indem man ein Testprogram schreibt und einige Tests laufen lässt sondern sowas muß beweisbar sein, auch auf dem Papier als Formel, also formale Korrektheit.

Gruß Hagen

[negaH]

Zitat:

Auch wenn die Rekursion vielleicht sogar in den meisten Fällen eine kurze und elegante Problem(lösungs)beschreibung liefert, so kann dennoch die Algorithmenoptimierung durchaus in einer Beseitigung der Rekursion zu suchen bzw. zu finden sein.

Ja, aber von der Priorität her erst als allerletztes Mittel (Ausnahmen bestätigen die Regel).
Und wie ich vorherig schon beschrieb gibt es nicht nur die schmale Sichtweise auf die ASICs, sondern die Frage "iterativ vs. rekursiv" lässt sich für jede Hardware stellen, zb. auch auf Papier, FPGAs uvm.

Gruß Hagen

[jfheins]

Also was Geschwindigkeitsoptimiereung angeht halte ich mich an diese Rangliste:
(absteigend nach Wichtigkeit)
1. verwendeter Algorithmus
2. Art der Implementierung
3. Programmierspache

=> Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet, solange man es vernüftig macht.

[negaH]

Zitat:

=> Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet...

Aus Sicht der Performance-/Speicherunterschiede. Aber meiner Meinung nach eben nicht aus Sicht der Verständlichkeit und Wartbarkeit.

Gruß Hagen

[Delphi-Laie]

Zitat:

Zitat von negaH (Beitrag 1028044)

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.