Rekursion ist, wenn etwas rekursiv ist.

Also, äh, wenn etwas sich selbst benötigt, um sich zu definieren. Die Fibionacci-Zahlen sind durch einen Anfangszustand sowie sich selbst definiert. Die natürlichen Zahlen auch: "0 ist eine natürliche Zahl. Der Nachfolger einer natürlichen Zahl ist eine natürliche Zahl" (war doch so, oder?). Man sollte zwischen rekursiver Definition und rekursiven Algorithmen unterscheiden.
Rekursive Addition:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9:
| Procedure SillyAdd (a,b : Integer) : Integer; Begin If b < 0 Then Result := Add (a-1, b+1) Else If b > 0 Then Result := Add (a+1, b-1) Else Result := a End; |
Super, oder? Nicht gerade optimal, aber rekursiv.
Hatte mich 1,5 Tage ausgeklinkt und nun dies hier: Super interessante Diskussion mit vielen Aspekten: Performance, Laufzeitverhalten, Unverständnis:
Ich will mich hier kurz zu meinem Statement äußern, die Natur ansich sei rekursiv. Witzig, das hier gleich die Fortpflanzung als Beispiel genannt wird: Die ist nicht rekursiv, sondern .... Lassen wir das.
Ich meine die 'Selbstbeinhaltung' in der Natur. Sie hat es geschafft, mit einem 4 bit Code und einem Grundprogramm (Gene) eine Vielfalt an Dingen zu erschaffen, die jedes für sich ein Wunder ist. Ist doch irre, oder? Wäre so, als ob nur durch das Betriebssystem bereits klar ist, das ein Programm funktioniert.
Gene schaffen Zellen (natürlich mit Zwischenschritten), die dann Zellcluster schaffen, die dann Leben schaffen, das dann darüber nachdenkt, wie Gene funktionieren. Nebenbei schafft das Leben auch wieder Gene... usw.
Selbst in der Ausprägung der Dinge (Pflanzen, Tiere etc.) treffen wir auf Rekursion. Das Aussehen von Bäumen, Farnen, Küstenlinien etc. ist durch einfache rekursive Routinen so realistisch zu zeichnen, das man den Unterschied nicht merkt.
Was Performance anbelangt, gibt es eine Anekdote aus meinem Familienkreis: Mein Vater hatte sich in den 60er und 70er Jahren hauptberuflich mit Algorithmen und Datenstrukturen befasst. Er verfasste ein Buch über Sortieralgorithmen, darunter Quicksort (logischerweise). Die iterative Implementierung über einen handgebissenen Stack war wesentlich performanter, als die elegante rekursive Implementierung. Das war ca. 1970 auf alten HP Boliden in Landmaschinenbauweise. Auf Rechnern neuerer Architektur ist der rekursive Ansatz der bei weitem Schnellere. Vermutlich kommt die Mär vom langsamen rekursiven Ansatz daher, dass unsere Lehrer das von ihren Lehrern so beigebracht bekommen haben.
Solange die iterative Lösung eines Problems nur die Umsetzung der Rekursiven mit Hilfe von Stacks etc. ist, sollte man die rekursive Lösung vorziehen. Aber meistens gibt es noch einen iterativen Ansatz, der nun aber gar nichts mit dem Rekursiven zu tun hat.
Beispiel Baumsuche: Wenn ich direkten Zugriff auf die Blätter und Knoten habe, muss ich mich nicht rekursiv durchhangeln. (TTreeView.Items z.B.)
Beispiel Permutation: Wenn ich Graycodes kenne, muss ich meine Permutationen nicht rekursiv durchrechnen.
Spanning Trees gehen wunderbar iterativ, ohne rekursive Klimmzüge
Teilweise ist das dann wirklich wesentlich schneller.