Rekursion vs. Iteration

[negaH]

Zitat von gammatester:

Vielleicht sollten wir uns erst einmal einigen, was unter Algorithmus zu verstehen ist. Es geistern hier "Algorithmus", "Algorithmen-Basis", "Problem-Stellung" usw durcheinander.

Und natürlich ist es sinnvoll, den "Apfel"-Algorithmus mit exponentieller Laufzeit mit dem "Birnen"-Algorithmus mit logaritmischer Laufzeit zu vergleichen, uns sei's nur darum, umherauszufinden welcher ein bestimmtes Problem "besser" löst.

"Besser" kann situationsabhängig sein: Wenn ich schnell ein Problem lösen muß bis n=10, ist es ev. "besser" einen quick-und-dirty O(2^n)-rekurven Algorithmus in 5 min zu implementieren, als einen hochoptimierten O(log(n)) iterativen, der aber erst ab n>1000 schneller ist und nach 5 Tagen fertig ist.

Naja, aber für einen fairen Vergleich "iterativ vs. rekursiv" sollte man schon sich auf ein und den selben Algorithmus beziehen.

Problemstellung -> Formel/Algortihmus -> Implementierung auf jeweiliger HW mit spezifischer SW -> rekursiv vs. iterativ

Das wäre mein Vorschlag.

Das Aufwand-Nutzen-Verhältnis sollten wir aussen vor lassen.

Gruß Hagen

[negaH]

Zitat:

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:

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.

Na dann schau dir mal dieses Zitat an.

... warum Windows... lahmlegt.

Dir ist schon bewusst das wir hier "iterativ vs. rekursiv" diskutieren ? Und du führst als Agrumentation Windows oder Assembler an. Jeder geht dann davon aus, besonders weil du pro "iterativ" argumentierst, das somit Windows langsammer wurde weil es rekursive Implementierungen bevorzugt.

Zitat:

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.

Dann lese das entsprechende Posting nochmal. Und ja wenn es Unterschiede final gibt dann kann das nur an der HW liegen. Sprich zusätzlicher CALL + Einrichten des Stacks und damit mehr Speicher bei rekursiven Impl. im Vergleich zur iterativen.

Gruß Hagen

[Delphi-Laie]

Zitat von negaH:

Na dann schau dir mal dieses Zitat an.

... warum Windows... lahmlegt.

Dir ist schon bewusst das wir hier "iterativ vs. rekursiv" diskutieren ? Und du führst als Agrumentation Windows oder Assembler an. Jeder geht dann davon aus, besonders weil du pro "iterativ" argumentierst, das somit Windows langsammer wurde weil es rekursive Implementierungen bevorzugt.

Nun mal halblang. Du kannst mich dafür verantwortlich machen, daß Du in meine Aussagen etwas hineindichtest und sie damit fehlinterpretierst. Erst recht steht es Dir nicht zu, für alle zu sprechen. Ich weiß genau, was ich schrieb und krame es extra noch mal für Dich hervor:

„Manchmal habe ich sogar den Verdacht, daß absichtlich Bremsschleifen dorthinein implementiert wurden.“

Dort steht etwas von Schleifen (das sind Iterationen!), nicht jedoch von Rekursion. Also, wenn man schon jemanden zitiert, sollte man dabei auch redlich und sorgfältig vorgehen und nicht versuchen, jemanden daraus einen Strick zu drehen.

[Daniel]

Schön, dann können wir ja jetzt wieder zu den fachlichen Aspekten der Frage übergehen.

[negaH]

Ok, gehen wir es mal systematisch an.

Wir wollen wissen ob eine "rekursive" Schreibweise ein und des selben Algorithmus im Gegensatz zu einer "iterativen" Schreibweise in einer Programmiersprache die keine der beiden Seiten bevorzugt auf einer Hardware die ohne zusätzliche Performance- und Speicherunterschiede beim Aufruf von Unterfunktionen, einen Unterschied machen.

Wir stellen uns eine Programmiersprache vor in der man ein Algo. sowohl iterativ wie auch rekursiv schreiben kann. Der dahinter liegende Compiler bzw. die Synthese zerlegt unseren geschriebenen Quelltext so das sie mit Boolscher Analyse die rekursive Variante in die iterative überführen kann oder umgekehrt. D.h. aus Sicht des erzeugten Resultates wird der Maschinencode für ASCIs oder das Bitfile für FPGAs bei beiden Schreibweise absolut identisch sein. Somit schließen wir Hardwareunterschiede mal komplett aus. Bei FPGAs ist es auch exakt so und nicht anders.

Was bleibt ?

Zwei Quelltexte die ein und den selben Algorithmus oder meinetwegen Formel beschreiben.
Es ist nun so das Mathematiker die solche Formeln aufschreiben sie fast immer rekursiv aufschreiben zb. in Polnischer Notation.
Es ist aus Sicht der Resourcen/Performance egal ob man nun im Quelltext diese Formel rekursiv oder iterativ aufschreibt. Wie oben schon definiert wird der Compiler/Synthese sowie so diese Quelltexte in ein und das selbe Resultat umwandeln. Das interessiert uns nicht.

Der Unterscheid ist:
- rekursive Formel -> rekursiver Algo -> rekursiver Quelltext
- rekursive Formel -> iterativer Algo -> iterativer Quelltext

Wäre es nun aus Sicht der Verständlichkeit nicht besser alles rekursiv zu machen ?

Ein weiterer Unterschied ist das man bei rekursiven Schreibweisen eine Menge an redundanten Wiederholungen einspart. Das ist ja auch der Grund warum Mathematiker/Informatiker bevorzugt solche Probleme rekursiv formulieren und implementieren.

Wir haben also einen Algo mit Komplexität X. Egal ob rekursiv oder iterativ implementiert, diese Komplexität muß erhalten bleiben da man ansonsten Äpfel mit Birnen vergleicht. Wir haben eine Hardware und einen Programmiersprache die in beiden Fällen keine der beiden bevorzugt.
Ergo: am Ende sind die Resultate in Punkto Komplexität, Performance und Resourcenverbracuh exakt identisch. Einzigst die Schreibweise macht einen Unterschied. Da man über die rekursive Schreibweise eine bessere Verständlichkeit erreicht, auf Grund des Weglassen von reduntanten Formelbestandteilen, muß die rekursive Variante im Allgmeinen besser Verständlich sein und damit wartbarer.

Gruß Hagen

[idefix2]

@ jfheins:

Jetzt erinnere ich mich, über die Transformation bin ich in meinem Studium auch einmal gestolpert, habs in der Zwischenzeit wieder vergessen. Ist ein sehr eleganter rekursiver Ansatz.

Fairerweise muss man aber sagen, dass es doch ein ganz anderer Algorithmus ist, als der in der iterativen Variante verwendete. Vor allem aber erfordert er sehr langes Nachdenken, um dahinterzukommen, wie das Ding funktioniert, ich habe das damals gemacht und WILL es eigentlich gar nicht mehr nachvollziehen - was aber der Intention, lesbare und leicht verständliche Programme zu erstellen, eigentlich diametral entgegengesetzt ist.

[idefix2]

Zitat:

Deshalb friemelte ich für alle Klugheitsausscheider mal eben - so auf die Schnelle - ein kleines (natürlich Delphi-)Programm zusammen, das beide Algorithmen bei Fibonacci vergleicht. Ich hoffe, das das Hochladen desselben klappte.

Wie ich in meinem Post 58 geschrieben habe - eine schlechte Implementierung kann für schlechte Performance sorgen, auch bei iterativen Verfahren. Einen untauglich implementierten rekursiven algorithmus mit einem brauchbar implementierten itetrativen Algorithmus zu vergleichen, beweist gar nichts.

Es kommt auch bei iterativen Verfahren vor, dass man rechenaufwändige Zwischenergebnisse später wieder braucht, da bringst Du die Performance in der gleichen Weise in den Keller, wenn Du die Zwischenergebnisse immer wieder neu berechnest.

[Delphi-Laie]

Zitat von idefix2:

Zitat:

Deshalb friemelte ich für alle Klugheitsausscheider mal eben - so auf die Schnelle - ein kleines (natürlich Delphi-)Programm zusammen, das beide Algorithmen bei Fibonacci vergleicht. Ich hoffe, das das Hochladen desselben klappte.

Wie ich in meinem Post 58 geschrieben habe - eine schlechte Implementierung kann für schlechte Performance sorgen, auch bei iterativen Verfahren. Einen untauglich implementierten rekursiven algorithmus mit einem brauchbar implementierten itetrativen Algorithmus zu vergleichen, beweist gar nichts.

In dieser Diskussion finden sich pauschale Äußerungen, daß rekursiv dem Iterativen ebenbürtig ist, und das ist so pauschal eben falsch. Nunmehr wird - von Dir - bei rekursiv zwischen „brauchbar“ und „untauglich implementiert“ unterschieden. Daß der Algorithmus als solcher selbst bzw. an sich ein schlechteres Laufzeitverhalten hat (haben kann), wird auch mit solchen Aussagen umschifft. Wie soll denn ein rekursiver Algorithmus, der auf der Gleichung

fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)

beruht oder aufbaut, „tauglich implementiert“ werden?

[negaH]

Zitat:

In dieser Diskussion finden sich pauschale Äußerungen, daß rekursiv dem Iterativen ebenbürtig ist, und das ist so pauschal eben falsch.

Dann beweise das bitte. Ich behaupte das es da keinen Unterschied geben darf und wird aus Sicht des Resultates wenn man einen fairen Vergleich anstellt.

Es unterscheidet sich ausschließlich nur die Schreibweise im Quelltext. Es verbleiben nur noch konstruktiv die Argumente, was ist verständlicher und damit wartbarer.

Gruß Hagen

[Mithrandir]

Leude...

Meint ihr nicht, ihr habts langsam? Ich dreht euch dauernd im Kreis, seit mindestens 6 Seiten. Wenn ihr Bock darauf habt, tausch euch per PN aus und postet das Resultat hier. So kommt ihr jedenfalls kein Stückchen weiter.