Rekursion vs. Iteration

[Delphi-Laie]

Mit Tatsachen läßt sich bekanntlich am schlechtesten diskutieren - nämlich gar nicht.

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.

Bei größeren Eingabewerten steigt die Berechnungszeit bei der Rekusrsion spürbar gegenüber der Iteration. Ich vermute mithin exponentielle Komplexität (ohne Gewähr) gegenüber linearer.

Daß daran nur die Hardware schuld sein soll, lasse ich mir von niemanden aufbinden.

@mkinzler: Ich weiß nicht, über wen Du herzogst, anscheinend über mich. Es ist schäbig, öffentlich in der dritten Person über jemanden sich abfällig zu äußern. Besonders unwürdig ist es bei einem Moderator und einer Person Deiner Bildung. Ich hoffe nicht, daß auch in diesem Forum irgendwann einmal Delphi-Treff-Verhältnisse einziehen werden.

[negaH]

Zitat von Delphi-Laie:

Mit Tatsachen läßt sich bekanntlich am schlechtesten diskutieren - nämlich gar nicht.

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.

Bei größeren Eingabewerten steigt die Berechnungszeit bei der Rekusrsion spürbar gegenüber der Iteration. Ich vermute mithin exponentielle Komplexität (ohne Gewähr) gegenüber linerarer.

Daß daran nur die Hardware schuld sein soll, lasse ich mir von niemanden aufbinden.

@mkinzler: Ich weiß nicht, über wen Du herzogst, anscheinend über mich. Es ist schäbig, öffentlich in der dritten Person über jemanden sich abfällig zu äußern. Besonders unwürdig ist es bei einem Moderator und einer Person Deiner Bildung. Ich hoffe nicht, daß auch in diesem Forum irgendwann einmal Delphi-Treff-Verhältnisse einziehen werden.

Tja, Glashaus und Porzelanladen. Schade eigentlich. Bin somit weg.

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.

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

[jfheins]

Zitat von Delphi-Laie:

Mit Tatsachen läßt sich bekanntlich am schlechtesten diskutieren - nämlich gar nicht.
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.
Bei größeren Eingabewerten steigt die Berechnungszeit bei der Rekusrsion spürbar gegenüber der Iteration. Ich vermute mithin exponentielle Komplexität (ohne Gewähr) gegenüber linerarer.
Daß daran nur die Hardware schuld sein soll, lasse ich mir von niemanden aufbinden.
@mkinzler: Ich weiß nicht, über wen Du herzogst, anscheinend über mich. Es ist schäbig, öffentlich in der dritten Person über jemanden sich abfällig zu äußern. Besonders unwürdig ist es bei einem Moderator und einer Person Deiner Bildung. Ich hoffe nicht, daß auch in diesem Forum irgendwann einmal Delphi-Treff-Verhältnisse einziehen werden.

Keine Angst, die Hardware ist nicht schuld. Du bist schuld.
Das rekursive ist ein schlechterer Algorithmus, und damit klar unterlegen. Das hat nichts mit rekursion vs. iteration zu tun, sondern mit guter vs. schlechter Algorithmus.
Benutze einen Algorithmus aus Post #59 oder Post #59 und es sollte schneller laufen.

Genausogut kann ich einen rekursiven Quicksort gegen einen iterativen Bubblesort vergleichen. Und OMG OMG iteration ist ja TOTAL lahm, wenn man ein paar mehr Elemente nimmt


Es gibt Algorithmen, die sich besser so und besser so implementieren lassen. Fibonacci ist für mich etwas, was sich rekursiv sehr einfach schreiben lässt, dann aber unperformant wird, und daher die iterative Variante vorzuziehen ist. (Weil da weniger Lesbarkeit verloren geht gegenüber der performanten Rekursion)

[JasonDX]

Zitat von Delphi-Laie:

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.

Du hast es richtig erfasst: Du vergleichst Algorithmen, nicht Implementierungen. Vergleiche doch mal eine rekursive und eine iterative Implementierung des selben Algorithmus. Dann wirst du merken, dass dort kaum ein Unterschied vernehmbar ist.
Andernfalls... Ich friemle mal für dich (deine Worte) Klugheitsausscheider mal ein kleines Programm zusammen, das eine Liste von Zahlen sortiert. Ich verwende die rekursive Implementierung von Quicksort, und eine iterative Implementierung von BogoSort. Das Ergebnis kannst du dir denken...
Du magst vielleicht Äpfel und Birnen vergleichen können - aber daraus kannst du keine Rückschlüsse auf Rind- und Schweinefleisch ziehen. Das tust du aber: Du vergleichst Algorithmen und schließt daraus auf Eigenschaften verschiedener Implementierungsverfahren... Fällt dir langsam dein Fehler auf?

greetz
Mike

[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 jfheins:

Benutze einen Algorithmus aus Post #59 oder Post #59 und es sollte schneller laufen.

Das ist durchaus möglich. Allerdings ist dieser Algorithmus - im Vergleich zur „vollrekursiven“ Variante - teilweise „entrekursiviert“ (Die, die Ihr Informatik studiert(et) - gibt es ein Verb dafür?) (worden). Die originale rekursive Definition der Fibonaccigliederberechnung findet sich dort jedenfalls nicht mehr. Wenn man einen vollrekursiven Algorithmus teilweise von der Rekursion befreit und sich dann eines Laufzeitverhaltens erfreut, das mit der Iteration mithalten kann - das ist m.E. kein plausibler Nachweis dafür, daß die Rekursion der Iteration ebenbürtig ist?! Denn gerade, weil die Rekursion es eben (vom Laufzeitverhalten bzw. der Komplexität) her nicht ist, ist sie in jenem Algorithmus teilweise entfernt worden.

[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