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

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

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

[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