Rekursion vs. Iteration

[JasonDX]

Zitat von Delphi-Laie:

Mich würde in diesem Zusammenhang allerdings einmal interessieren, ob bei Problemlösungen, die sowohl iterativ als auch rekursiv möglich sind, es auch Fälle gibt, in denen die Rekursion hinsichtlich des Laufzeitverhaltens der Iteration substantiell (also vom Komplexitätsverhalten her) überlegen ist.

Ich tendiere zu nein. Sollte ich die Zeit dafür finden, ließe sich evt. ein Beweis für die Äquivalenz beider Verfahren finden.

Zitat von Delphi-Laie:

Nachzuweisen, daß eine iterative einer (bestimmten) rekursiven Lösung überlegen ist, bedurfte es ja nur einer Folge, die schon seit dem späten Hochmittelalter (oder frühen Spätmittelalter) bekannt ist.

Ein klares Zeichen, dass du Beiträge entweder nicht liest oder nicht verstehst. Es ist bereits gezeigt worden, dass die iterative Lösung der rekursiven nicht überlegen ist. Tailrecursion is recursion! Bitte lese zukünftig Beiträge, bevor du ihnen widersprichst.

greetz
Mike

[negaH]

@Alzaimar

Zitat:

Das das nebenbei auch noch performanter ist, liegt an der Tatsache, das eine Schleife nun mal schneller ist

Das ist eben nicht richtig. Deine Aussage bezieht sich nur auf eine spezifische Hardware auf der dann Schleifen schneller laufen als zb. die gleiche Anzahl von Sprüngen zu Unterfunktionen.

Das gilt zb. für die Hardware FPGA oder Papier eben nicht mehr. Dort existiert kein Overhead im Speicher und Performance beim Aufruf von Unterfunktionen weil sie durch die Synthese eliminiert werden oder einfach nicht vorhanden sind.

Letzendlich sind es auch nicht "iterative" und/oder "rekursive" Verfahren. Sondern es ist ein und das selbe Verfahren das man schriftlich entweder iterativ oder rekursiv niederschreibt. Was am Ende in Hardware ankommt ist eine Frage der Compiler/Synthese und der Hardware selber.

Betrachtet man also die Frage "rekursiv vs. iterativ" unabhängig von Hardware dann sind sie identisch in ihrer Komplexität, Big O. Bezieht man die Hardware und Compiler etc.pp. mit in die Fragestellung ein dann muß man auch diese als Faktor berücksichtigen. Und erst da wird man dann leichte Nachteile der Rekursion gegenüber der Iteration haben wenn es sich zb. um ASICs handelt aber eben nicht bei FPGAs/CPLDs oder Quantenrechnern.

Dieser Overhead auf ASICs entsteht ausschließlich durch folgende Faktoren:
- zusätzliche CPU Takte sind nötig bei Sprüngen
- zusätzlicher Stack ist nötig zum Speichern der Rücksprungadresse und Einrichten des Stackframes der rekursiven Unterfunktion
- zusätzliche CPU Takte sind nötig für diese Stackeinrichtung und Stackbereinigung
- ein RET zum Aufrufer ist nötig

Das sind alles nur Faktoren auf Grund der CPU Architektur die eben Sprünge benachteiligt zu Programmcode der ohne diese auskommt wie bei iterativen Umsetzungen.

Als letztes kommt noch der Punkt hinzu das zb. der Delphi Compiler nicht über Funktionsrümpfe hinweg optimieren kann. Er wird also besser eine iterative Funktion optimieren können als deren rekursve Schreibweise.

Das alles sind aber Punkte die man bei der generellen Bewertung "iterativ vs. rekursiv" aussen vor lassen muß. Und dann ergibt sich wieder das gewohnte mathematische Bild das beide äquvivalente Schreibweisen der selben Sache sind und nichts mehr.

Wenn dem so ist wird nun auch logsich das man sich bei dieser Frage nur auf die Fragestellung: was ist verständlicher beziehen darf. Und das hängt letzendlich vom Algorithmus und der Zielsetzung ab. Bei bestimmten, wenigen Problemen ist die iterative Schreibweise einfacher zu verstehen, bei den meisten Problemen wird aber schon bei der Mathematik und deren Formel die rekusive Schreibweise bevorzugt da sie intuitiver und einfacher ist. Vernachlässigt man also mal den mariginalen Performance/Speicheroverhead der auf ASICs systembedingt einen Unterschied ausmacht dann ist in den meisten Fällen die rekursive Schreibweise die bessere Wahl. Nicht weil sie schneller sein könnte oder weniger Speicher verbraucht, das haben wir ja nun hinlänglich ausdiskutiert das dies nicht der Fall sein kann und darf, sondern weil sie angemessener ist und verständlicher.

Gruß Hagen

[negaH]

Zitat:

Das gilt zb. für die Hardware FPGA oder Papier eben nicht mehr. Dort existiert kein Overhead im Speicher und Performance beim Aufruf von Unterfunktionen weil sie durch die Synthese eliminiert werden oder einfach nicht vorhanden sind.

Betrachtet man mal die Harwdare Papier genauer in diesem Rahmen dann sind rekursive Scheibweisen sogar Speicher=Papier schonender als die meisten iterativen Schreibweisen. In diesem Fall kann man unter Berücksichtung "Harwdare ist Papier" sogar behaupten das rekursive Schreibweisen besser sind als iterative. Auch die Resource "Performance" ist in diesem Fall besser da man weniger Formeln eben schneller schreiben kann als mehr Formeln.

Gruß Hagen

[Delphi-Laie]

Zitat von JasonDX:

Zitat von Delphi-Laie:

Nachzuweisen, daß eine iterative einer (bestimmten) rekursiven Lösung überlegen ist, bedurfte es ja nur einer Folge, die schon seit dem späten Hochmittelalter (oder frühen Spätmittelalter) bekannt ist.

Ein klares Zeichen, dass du Beiträge entweder nicht liest oder nicht verstehst. Es ist bereits gezeigt worden, dass die iterative Lösung der rekursiven nicht überlegen ist. Tailrecursion is recursion! Bitte lese zukünftig Beiträge, bevor du ihnen widersprichst.

Zunächst einmal heißt es „lies“ (oder heißt die inzwischen aus der Mode gekommen Dateibezeichnung „lesemich.txt“?). Auch sollte ein Forumsverantwortlicher sich mit solchen indiskutablen Aussagen besser zurückhalten. Für diesen Umgangston seitens des Forumsstabes gibt es nämlich schon ein anderes Delphi-Forum. Ich verstand zudem sehr wohl, daß man Iterationen auch über Rekursion (bzw. umgekehrt) abbilden kann, daß es da eine Äquivalenz gibt.

Ich dachte eigentlich, daß ich mich klar genug ausdrückte: Einer bestimmten rekursiven Lösung. Es gibt auch eine andere, für die das nicht gilt.

Ich werde Dir mal ein Gleichnis, das mit Programmierung nun überhaupt nichts zu tun hat, offenbaren: In meiner Schulklasse stritt sich mal ein Schüler mit einer Lehrerin, ob man ein Pflänzlein nur in einen größeren Blumentopf umpflanzt oder ob es auch in einen der gleichen Größe möglich bzw. sinnvoll ist. Die Lehrerin meinte, ein größerer sei nicht zwangsläufig, der Schüler schon. Schon damals spürte ich und auch heute bin ich noch der Meinung, daß jeder auf seine Weise recht hatte. Und so etwa kommt mir das mit den iterativen Rekursionen wenigstens bei dem hier so strapazierten Beispiel der Fibonacci-Berechnung auch vor: Natürlich kann man auch eine Rekursion dort hineinwürgen, wenn man denn unbedingt eine haben möchte, weil man sie so sehr mag, aber die eingangs so hochgelobten Vorteile wie Übersichtlichkeit, Wartbarkeit, geringeres Fehlerrisiko usw. bleiben dabei nach meiner Einschätzung voll auf der Strecke, sie sind jedenfalls nicht offensichtlich besser als bei der Iteration. Dafür stimmt aber das Laufzeitverhalten. Beides ist anscheinend wenigstens an diesem Beispiel nicht unter einen Hut zu bringen (weshalb ich die Pauschalität weiterhin negiere). Welchen Vorteil nun eine solche Rekursion gegenüber der Iteration hat, weiß ich immer noch nicht, aber ich möchte es nunmehr auch nicht mehr wissen.

[jfheins]

Zitat von Delphi-Laie:

Ich verstand zudem sehr wohl, daß man Iterationen auch über Rekursion (bzw. umgekehrt) abbilden kann, daß es da eine Äquivalenz gibt.

Das ist schön, das habe ich nämlich immer wieder bezweifelt.

Zitat von Delphi-Laie:

Natürlich kann man auch eine Rekursion dort hineinwürgen, wenn man denn unbedingt eine haben möchte, weil man sie so sehr mag, aber die eingangs so hochgelobten Vorteile wie Übersichtlichkeit, Wartbarkeit, geringeres Fehlerrisiko usw. bleiben dabei nach meiner Einschätzung voll auf der Strecke, sie sind jedenfalls nicht offensichtlich besser als bei der Iteration.Dafür stimmt aber das Laufzeitverhalten. Beides ist anscheinend wenigstens an diesem Beispiel nicht unter einen Hut zu bringen

Richtig. Das liegt daran, dass sich für Fibonacci die iterative Problemlösung besser eignet. Das heißt aber nicht dass Iteration allgemein und immer besser ist, sondern bei diesem Problem. Ich hatte das Gefühl, du verallgemeinerst das Beispiel. Siehe auch:

Zitat von alzaimar:

Wenn ich mir die rekursiven Lösungen zum Türme-Von-Hanoi-Problem anschaue, oder die Ermittlung von Permutationen, oder eine Lösung des N-Damen-Problems, dann verstehe ich nicht, wie man iterative Lösungen per se bevorzugen kann. Und wenn ich eine iterative Berechnung der Fakultät oder der Fibionacci-Folge sehe, verstehe ich auch nicht, wie man rekursive Lösungen per se bevorzugen kann.

Zitat:

(weshalb ich die Pauschalität weiterhin negiere).

Was negierst du? Du hast doch oben selbst gesagt, dass du verstanden hast dass man immer Rekursion auf Iteration abbilden kann und umgekehrt. Also eine 100% Äquivalenz was die Laufzeitkomplexität angeht.

Zitat:

Welchen Vorteil nun eine solche Rekursion gegenüber der Iteration hat, weiß ich immer noch nicht, aber ich möchte es nunmehr auch nicht mehr wissen.

Bei manchen Problemen (Fibonacci gehört nicht dazu) ist die rekursive Schreibweise leichter verständlich und übersichtlicher als die iterative. (Gleicher Algorithmus und damit gleiche Komplexität wohlgemerkt) Reicht das nicht?

[mkinzler]

Da bist du nunmal anderer Meinung wie wir. Wenn hier einer eine Behauptung aufstellt ohe diese wirklich zu belegen, andere Antworten ignoriert, andere diskussionsteilnehmer beleidigt, dann ist es durchaus unsere Aufgabe ihn darauf hinzuweisen!

[JasonDX]

Zitat von Delphi-Laie:

Zunächst einmal heißt es „lies“ (oder heißt die inzwischen aus der Mode gekommen Dateibezeichnung „lesemich.txt“?).

Es ist nunmal nicht jeder Deutscher in diesem Forum. Mir wärs eh lieber, wenn die ganze Diskussion auf englisch geführt werden würde. Aber danke für den Hinweis...

Zitat von Delphi-Laie:

Ich verstand zudem sehr wohl, daß man Iterationen auch über Rekursion (bzw. umgekehrt) abbilden kann, daß es da eine Äquivalenz gibt.

Ich dachte eigentlich, daß ich mich klar genug ausdrückte: Einer bestimmten rekursiven Lösung. Es gibt auch eine andere, für die das nicht gilt.

Du hast dich offensichtlich nicht klar genug ausgedrückt. Folgendes Zitat lässt auch relativ wenig Interpretationsmöglichkeiten offen:

Zitat von Delphi-Laie:

Nachzuweisen, daß eine iterative einer (bestimmten) rekursiven Lösung überlegen ist, bedurfte es ja nur einer Folge, die schon seit dem späten Hochmittelalter (oder frühen Spätmittelalter) bekannt ist.

Entweder du hast eine triviale Aussage getroffen (bspw. Quicksort rekursiv ist besser als Bogosort iterativ), woraus sich aber keine sinnvollen Schlüsse ziehen lassen können, und schon gar nicht für die Diskussion relevant sind, oder du sprichst hier eindeutig von der pauschalen Überlegenheit der iterativen Implementierung der Fibonaccifolge über der rekursiven. Kannst du diese dann begründen? Ich behaupte, die Endrekursive Variante ist mindestens so einfach zu erkennen wie die iterative, gleich schnell, dafür aber einfacher zu zeigen. Bis auf die Lesbarkeit, welche ein subjektiver Faktor ist, gibt es keine Begründung, warum die iterative Implementierung der rekursiven Überlegen sein soll. Ein objektiver Vorteil der rekursiven Variante ist die Trivialität, ihre Korrektheit zu zeigen. Lässt man subjektives Empfinden beiseite, wäre also die rekursive Variante tatsächlich der iterativen überlegen.

Zitat von Delphi-Laie:

Und so etwa kommt mir das mit den iterativen Rekursionen wenigstens bei dem hier so strapazierten Beispiel der Fibonacci-Berechnung auch vor: Natürlich kann man auch eine Rekursion dort hineinwürgen, wenn man denn unbedingt eine haben möchte, weil man sie so sehr mag, aber die eingangs so hochgelobten Vorteile wie Übersichtlichkeit, Wartbarkeit, geringeres Fehlerrisiko usw. bleiben dabei nach meiner Einschätzung voll auf der Strecke, sie sind jedenfalls nicht offensichtlich besser als bei der Iteration.

• Übersichtlichkeit: Das ist ein subjektives Empfinden. Es gibt Leute, die kommen mit 12 verschachtelten Schleifen besser klar als mit einer Rekursion, und es gibt Leute, bei denen es umgekehrt ist.
  Für mich ist die endrekursive Variante immernoch lesbarer als die iterative Schleife. Aber das ist wie gesagt Gewöhnungssache.
• Wartbarkeit: Einen 4zeiler, bei dem 1 Vergleich vorkommt, ist definitiv einfacher zu warten als eine Schleife, bei der sonstwelche Variablen rumgetauscht werden.
• geringeres Fehlerrisiko: Dieses ist bei der Rekursiven Variante immer gegeben. Rekursive Funktionen können sehr einfach bewiesen werden - Auch umformungen auf Endrekursion ect. Somit kann man auf Papier den rekursiven Ausdruck beweisen und 1:1 ins Programm übernehmen. Dies bietet definitiv weniger Fehlerpotential als eine iterative Schleife, da diese nicht so direkt von einem bewiesenermaßen korrekten Term in ein Programm überführt werden kann.

Die meisten Vorteile sind also immernoch gegeben, und die restlichen bleiben höchstens auf der Strecke des subjektiven Empfindens.

greetz
Mike

[Sharky]

Zitat von Delphi-Laie:

Zitat von JasonDX:

... Bitte lese zukünftig Beiträge, bevor du ihnen widersprichst.

Zunächst einmal heißt es „lies“ (oder heißt die inzwischen aus der Mode gekommen Dateibezeichnung „lesemich.txt“?). Auch sollte ein Forumsverantwortlicher sich mit solchen indiskutablen Aussagen besser zurückhalten. Für diesen Umgangston seitens des Forumsstabes gibt es nämlich schon ein anderes Delphi-Forum. ....

STOP
Hier wurde wohl nicht als "Forenverantwortlicher" gesprochen. Auch ist eine Diskussion über die richtige Schreibweise absolut unnötig. Deine Versuche jemandem ein schlechtes Verhalten im Forum unterzuschieben wurden schon bemerkt. Glube mir; es funktioniert hier ganz sicher nicht!

Wenn hier nur noch persönlich Anfeindungen vorgetragen werden werden wir im Team beraten und dann denn Thread schliessen.

P.S.: aus der englischen Word readme auf das richtige deutsche Wort zu schliessen zeigt sehr schön wie in diesem Thread argumentiert wird

[Delphi-Laie]

Markus Kinzler....

Zitat von mkinzler:

Da bist du nunmal anderer Meinung wie wir. Wenn hier einer eine Behauptung aufstellt ohe diese wirklich zu belegen, andere Antworten ignoriert, andere diskussionsteilnehmer beleidigt, dann ist es durchaus unsere Aufgabe ihn darauf hinzuweisen!

So etwas weise ich zurück, und zwar deshalb, weil Du - obwohl Moderator - m.E. nicht neutral bist. Wo warst Du, als mich jemand absichtlich (?) und öffentlich in dieser Diskussion zu meinem Ungunsten fehlinterpretierte, was ich zudem leicht widerlegen konnte, und damit emotionale Spannung erzeugte?


Zurück zum Thema. Ich ließ mir absichtlich ein wenig Zeit für eine erneute Antwort. In dieser Diskussion wurde m.E. teilweise sogar erheblich aneinander vorbeigeredet. Richtig ist, rein formal und von der Definition her, daß Rekursion dadurch charakterisiert ist, daß sich Programmteile (immer Unterprogramme?) (ggf. wiederholt) selbst aufrufen. Rekursion und Iteration kann man in bestimmter Weise aufeinander abbilden (es gibt sozusagen eine Schnittmenge). Die folgliche Kongruenz, ja fast schon Äquivalenz von Rekursion und Iteration führe ich zu folgendem absurden Höhepunkt:

Delphi-Quellcode:

procedure rekursion;
begin
rekursion
end

versus

Delphi-Quellcode:

repeat 
until false

Gibt es einen substantiellen Unterschied zwischen beiden Programmteilen, insbesondere hinsichtlich ihres Laufverhaltens? Anscheinend nein, denn beides sind Endlosschleifen (abgesehen davon, daß erstere den Stack schnell überlaufen läßt). Zudem ruft süffisanterweise sich im 2. Codeschnipsel auch die Schleife selbst immer wieder auf, es ist also auch sich selbst (immer wieder) aufrufender Code!

Ist es also das, was der Originalposter wohl gemeint haben mag, als er Rekursion und Iteration gegeneinander antreten ließ? Ganz sicher und offensichtlich nicht, denn damit wäre eine solche Gegenüberstellung überflüssig.

Was ich in dieser Diskussion bisher von keinem Diskussionteilnehmer las, werfe ich jetzt deshalb hier ein: Rekursion ist eine selbstähnliche Struktur, und weil wir im Bereich der Informatik sind, eine selbstähnliche Algorithmen-/Programmablaufstruktur (das ist nicht identisch)!

Das Wesen der Selbstähnlichkeit besteht darin, daß sich etwas selbst in gleicher oder wenigstens ähnlicher Gestalt selbst enthält. Nicht notwendig ist, daß die Teile erster Subordnung mehrmals vorhanden sind. Doch die Selbstähnlichkeit entfaltet erst ihre volle Pracht, ihr volles Wesen, wenn das gegeben oder zumindest möglich ist. Deshalb folgende Unterscheidungen:

1. Jedes Element enthält sein eigenes Abbild in der jeweils 1. Subebene nur einmal. So etwas ist z.B. bei der rekursiven Fakultät oder - im materiellen Bereich - bei den russischen Puppen namens Matrjoschka der Fall. Ich bleibe dabei, daß eine solche Rekursion nur eine „Lightversion“ ist, da sie letztlich mit der Iteration konformläuft.

2. Die Anzahl der Elemente (=Subprozesse) kann größer als 1 sein, so z.B. in Bäumen (und so auch in hierarchischen Dateisystemen).

3. Die Anzahl der Elemente (=Subprozesse) ist sicher größer als 1, so z.B. bei der rekursiven Fibonacciglied(er)berechnung.

Erst in den Fällen 2 und 3 entfaltet die Rekursion ihr wahres Wesen: Sie ist elegant zu beschreiben (bzw. ist eine elgante Methode, Probleme zu lösen bzw. Problemlösungen darzustellen) und zu implementieren und führt zu kurzen, sicher auch gut wartbaren Quelltexten. Das Laufzeitverhalten ist dagegen eher mau, denn diese Baumstruktur des Prorgrammablaufes beim Aufrufen der rekursiv aufgerufenen Unterprogramme x. Ordnung führen mit ziemlicher Sicherheit zu mindestens exponentiellem Laufzeitverhalten (bei der Fakultät z.B. sogar zu hyperexponentiellem Wachstum). Wollte man solche rekursiven Algorithem in adäquate iterative transformieren, so ist das entweder unmöglich (?), sehr aufwendig (wie es hier jemand bezüglich Fibonacci andeutete) oder nur unbefriedigend (s. Quicksort, falls R. Sedgewicks Aussage immer noch aktuell ist) möglich.

Ich hoffe, daß ich das Eingangsthema nunmehr wieder so aufgriff, wie es vermutlich (?) gemeint war/ist, und auch, daß mein Standpunkt nunmehr nachvollziehbarer ist.

[Daniel]

Zitat von Delphi-Laie:

Zudem ruft süffisanterweise sich im 2. Codeschnipsel auch die Schleife selbst immer wieder auf, es ist also auch sich selbst (immer wieder) aufrufender Code!

Und genau das halte ich für unpräzise. Die Schleife (nun nicht gerade Dein Beispiel, aber allgemeine Schleifen) enthalten Code, der wiederholt ausgeführt wird. Du hast ja völlig korrekt angemerkt, dass im ersten Beispiel der Stack zum Problem wird und das ist der substantielle technische Unterschied zwischen beiden Varianten. In der zweiten Variante springt der Programmzeiger zum Anfang der Schleife, der Kontext bleibt gleich. In der ersten Variante, der Rekursion, wird eine frische, neue Funktion mit ihren eigenen frisch initialisierten lokalen Variablen aufgerufen. Es mag sein, dass am Ende beide Fassungen zum gleichen Rechenergebnis kommen, aber das Verhalten zur Laufzeit ist für meine Begriffe gänzlich unterschiedlich.

Zitat von Delphi-Laie:

Das Laufzeitverhalten ist dagegen eher mau, denn diese Baumstruktur des Prorgrammablaufes beim Aufrufen der rekursiv aufgerufenen Unterprogramme x. Ordnung führen mit ziemlicher Sicherheit zu mindestens exponentiellem Laufzeitverhalten (bei der Fakultät z.B. sogar zu hyperexponentiellem Wachstum).

Und warum das Laufzeitverhalten per se mau sei, kann ich aus Deinem Beitrag immer noch nicht entnehmen. Kannst Du die Formulierung "exponentielles Verhalten" präzisieren? Ich kenne z.B. exponentielles Wachstum - aber nicht exponentielles Verhalten.