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