Markus Kinzler....
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
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.