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

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

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

[Delphi-Laie]

Zitat von Daniel:

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.

Laufzeitverhalten schrieb ich.

Dann gehe mal einen rekursiven Algorithmus (im engeren Sinne, wie ich es ausführlich beschrieb), während er abläuft (also den Prozeß seines Ablaufes) durch: Die hierarchieniedrigsten Aufrufe sind die häufigsten! Konkret z.B. beim rekursiven Fibonacci: Fib(0) bzw. Fib(1) werden am häufigsten berechnet. Ziseliert man diesen Prozeß (graphisch), entsteht eine Baumstruktur. Und die Anzahl der Elemente von Bäumen ist - soweit ich weiß - exponentiell.

Edit: So allgemein gilt das doch nicht. Beim Quicksort ist das Laufzeitverhalten viel günstiger (logarithmisch), allerdings gibt es dort keine Mehrfachaufrufe: Was sortiert ist, wird nie wieder vom Algorithmus berührt (vielleicht ist das schon der Grund für die gute Komplexität?!), im Gegensatz zu den vielen Mehrfachberechnungen bei z.B. dem rekursiven Fibonacci. Das mehrmalige (konkret immer zweifache) Aufrufen von hierarchiegleichen Subprozessen (wie im Vorbeitrag ausgeführt) ist aber auch hier gegeben.

[JasonDX]

Zitat von Delphi-Laie:

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

Diese Schnittmenge ist die Menge der derzeit berechenbaren Sprachen.

Zitat von Delphi-Laie:

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

Das Laufzeitverhalten eines Algorithmus ist nicht von der Art seiner Implementierung abhängig. Man kann relativ einfach aus einem iterativen Programm ein Rekursives erstellen, und umgekehrt. Mit selbem Laufzeitverhalten. Wenn du möchtest, kann ich dir zumindest die Idee dahinter erklären, auch wenns dann etwas theoretisch werden könnte.

Zitat von Delphi-Laie:

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.

Was genau meinst du mit "konformlaufen"? Dass sich die Rekursion auf einen iterativen Ablauf zurückführen lässt? Dann ist jede Rekursion eine "Lightversion".

Zitat von Delphi-Laie:

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

Das hängt ganz von der Berechnungsmethode ab. Nimmt man die triviale Implementierung, so ist die Anzahl der direkten Unteraufrufe entweder 0 oder 2. Überträgt man diese Berechnung in eine iterative Form (ohne optimierungen, welche ja auch nicht für die Rekursion angewant wurden), so wird lediglich der Rekursionsbaum traversiert. Folglich hätte dann die iterative Variante das selbe Laufzeitverhalten.
Optimiert man die Algorithmen, so erhält man neue Berechnungsmethoden, und ein (hoffentlich) besseres Laufzeitverhalten. Aber es gelten immernoch die gleichen Bedingungen: Gibt es einen Algorithmus, der die n-te Fibonaccizahl in t(n) berechnet, so gibt es sowohl eine iterative, als auch eine rekursive Implementierung, die in Theta(t(n)) läuft.

Zitat von Delphi-Laie:

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 ist sogar auch bei 1. der Fall. Es gibt keine schönere Definition von Listen als die rekursive; insb. für theoretische Analysen.

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

Die Laufzeit hängt von einem Algorithmus ab, nicht ob er rekursiv oder iterativ beschrieben wird. Beide sind gleichmächtige Beschreibungsformen. Der einzige Grund, warum Rekursion als langsamer empfunden wird als Iterationen ist der, dass 1. Die iterative Variante meist optimiert ist (Siehe bspw. Fibonacci), und 2. Ein Funktionsaufruf aufgrund der darunterliegenden Hardware länger braucht.

Zitat von Delphi-Laie:

Wollte man solche rekursiven Algorithem in adäquate iterative transformieren, so ist das entweder unmöglich (?) (1), sehr aufwendig (wie es hier jemand bezüglich Fibonacci andeutete)(2) oder nur unbefriedigend(3) (s. Quicksort, falls R. Sedgewicks Aussage immer noch aktuell ist) möglich.

Zu (1): Es ist (laut theoretischen Beweisen) immer möglich. Eine adäquate Implementierung wäre das iterative traversieren des Rekursionsbaumes. Inwiefern das aufwändig (2) ist, hängt eher von der Beschreibungssprache ab. Ob die Implementierung unbefriedigend (3) hängt in erster Linie von den Erwartungen ab. Lesbar ist eine solche generische Übertragung eher nicht; Aber das hängt in erster Linie von der Funktion ab, inwiefern diese eine lesbare iterative Implementierung erlaubt.


Was mir bisher eigentlich immer aufgefallen ist: Wenn ich mit Leuten über Rekursion ect. diskutiert habe, so waren das fast immer Leute, welche sich in erster Linie mit iterativen Programmiersprachen befasst haben. Vor 2 Jahren war ich rekursiven Implmentierungen zwar nicht abgeneigt, habe aber nur einen sehr scheuen und vorsichtigen Blick dahingewagt, immer im Hinterkopf, dass mir der dahinterliegende Code meinen Stack zumüllt.
Beginnt man, sich (gezwungenermaßen *g*) damit ordentlich außeinanderzusetzen, so lernt man damit umzugehen, und die Vorzüge kennenzulernen. Menschen, die die Ideen bspw. hinter Haskell, OCaml oder Lisp verstanden haben, musste ich noch nie von den Vorteilen von Rekursionen überzeugen - nur jene, die sich bisher noch nicht wirklich damit außeinandergesetzt haben.


greetz
Mike

[Delphi-Laie]

Zitat von JasonDX:

Zitat von Delphi-Laie:

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.

Was genau meinst du mit "konformlaufen"? Dass sich die Rekursion auf einen iterativen Ablauf zurückführen lässt?

Zumindest die, die in Internetamateurenzyklopädie sicher aus gutem Grundes als „iterative“ Rekursion bezeichnet wird.

Zitat von JasonDX:

Dann ist jede Rekursion eine "Lightversion".

Das ist die entscheidende Frage. Jede Iteration läßt sich als Rekursion darstellen, denn letztlich rufen - in gewisser Weise - sich Schleifen auch nur selbst immer wieder auf.

Doch ist jede Rekursion auch als Iteration abbildbar? Dazu fehlen mir die Kenntnisse. Ist das schon bewiesen worden? In Robert Sedgewicks Standardwerk z.B. stand zur Quicksort, daß sich das nur unbefriedigend als Iteration darstellen/umsetzen läßt. Während der Implementation wurde mir rasch klar, daß mit der dort vorgestellten Quelltext letztlich nur die Stackhandhabung emuliert/simuliert wird, es also eine verkappte Rekursion ist.

Sollte die letzte Frage tatsächlich bejaht werden können, bliebe auf jeden Fall der Vorteil der kurzen, übersichtlichen Problem(lösungs)beschreibung sowie der Quelltexte mit gleichen Eigenschaften, zudem gut wart- und portierbarer Quelltexte.

Edit: Weiter oben schriebst Du, daß es laut „theoretischen Beweisen“ (Anmerkung: Derlei Beweise sind immer theoretisch) möglich sei. Das überlas ich zunächst.

[Codewalker]

Ich habe auf die Schnelle keine Quelle gefunden, die es explizit auf Iteration zurückführt, aber es gibt Funktionen, die insbesondere im Compilerbau Kopfschmerzen machen, nämlich nicht-primitiv-rekursive Funktionen (Ackermannfunktion, Busy Beaver, Sudanfunktion, etc.).
Ich meine mich zu erinnern, dass man die nicht einfach auf eine iterative Variante zurückführen kann.