Rekursion: Elegant aber unpraktikabel?

I.MacLeod · Beiträge: 109

delfiphan hat folgendes geschrieben:

Ich muss Gausis Aussage etwas relativieren.

Erstens kann man Fibonacci sehr wohl rekursiv berechnen. Die Zahlenreihe ist ja auch rekursiv definiert!

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

procedure Fibonacci(x1, x2: Integer);
var
 x3: Integer;
begin
  x3 := x1+x2;
  Memo1.Lines.Add(IntToStr(x3));
  if x3 > 100 then // Abbruch
   Abort;
  Fibonacci(x2,x3);
end;

Genau genommen ist das nichtmal wirklich rekursiv, weil es nur einen Funktionsaufruf gibt, der am Ende der Funktion steht, nicht irgendwo zwischendrin - es ist also eine extrem ungünstig umgesetzte Schleife. :mrgreen:

@mimi: Da wird Rekursion wohl keine Probleme bereiten. Für eine iterative Variante müsstest du Zusätzlich noch Listen verwenden.

@hansa: www.linux-related.de...oding/o-notation.htm

_________________
{$APPTYPE CONSOLE}uses SysUtils;const a='{$APPTYPE CONSOLE}uses SysUtils;const a=%s;begin write(Format(a,[#39+a+#39]))end.';begin write(Format(a,[#39+a+#39]))end.

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

I.MacLeod hat folgendes geschrieben:

Genau genommen ist das nichtmal wirklich rekursiv, weil es nur einen Funktionsaufruf gibt, der am Ende der Funktion steht, nicht irgendwo zwischendrin - es ist also eine extrem ungünstig umgesetzte Schleife.

Dann definier mir, was eine Rekursion ist.

alzaimar · Verfasst: Sa 04.06.05 20:37

Rekursion ist, wenn etwas rekursiv ist. :wink:

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:

markieren

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.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme