Entwickler-Ecke :: Thema anzeigen - Rekursion: Elegant aber unpraktikabel?

alzaimar - Do 02.06.05 21:39
Titel: Rekursion: Elegant aber unpraktikabel?

Hallo!

Mir ist aufgefallen, das Rekursion einerseits auf Programmierer eine sehr grosse Faszination ausübt, andereseits aber auch schlaflose Nächte bereitet. Hier im Forum gibt es eine ganze Reihe von Rookies, also Anfängern. Da ich selbst mal einer war, weiss ich noch ganz genau, welche gehirnakrobatischen Gedankenkamasutras ich anstellen musste, um endlich mal zu kapieren, wie das geht.

Ich finde, Rekursion ist die eleganteste Möglichkeit, ein (rekursiv definiertes) Problem zu lösen. Wenn die Rekursion nicht allzu tief ist, und der rekursive Algorithmus das Problem minimalistisch beschreibt, tendiere ich, das in meinen kommerziellen Projekten zu implementieren. Denn hier gilt bei mir: "Keep it simple".

Was meint ihr?

NCortex - Fr 03.06.05 00:15

eine rekursion ist, wenn sich eine funktion selbst aufruft.

zum beipsiel:

Delphi-Quelltext

1:
2:
3:
4:
5:

function fak(n:integer):integer;
begin
  if n = 1 then result := 1
   else result := n * fak(n-1);
end;

wenn du jetzt

Delphi-Quelltext

1:

fak(5);

aufrufst, so ist das ergebnis 5 * 4 * 3 * 2 * 1 also die Fakultät von 5.

alzaimar - Fr 03.06.05 08:33

@Blackheart:Angefangen habe ich vor 30 Jahren.
Mir ist hier aufgefallen, das viele "Anfänger" Probleme mit Rekursion haben. Die werden gleich mit der 'Expertenmeinung' bombardiert, Rekursion sei 'uncool'. Das Problem dabei ist, das Rekursion einerseits fundamental wichtig für das Verständnis von Verfahren und Lösungen allgmemein und Algorithmen im Besonderen ist. Die Mechanik der Natur ist rekursiv. Selbstbeinhaltung ist der allumfassende Generator von Formen und Farben in der Natur. Schau dir solch profanen Dinge wie Sonnenblumen, Farne, Bäume, Küstenlinien etc. an. Das Alles ist durch Rekursivität definiert.

Andererseits ist Rekursivität auch widerum hinderlich bei der Implementierung effizienter Algorithmen: Wer käme schon ernsthaft auf die Idee, z.B. Fibionaccizahlen rekursiv zu implementieren (Fib (x) = Fib (x-1) + Fib (x-2) bzw. = 1, wenn x < 2)?

Als Anfänger kann ich das noch gar nicht verstehen. Es ist ähnlich wie mit dem Fahrradfahren: Erst fällst Du ständig auf die Schnauze und fragst Dich, wieso das verdammte Ding überhaupt geradeaus fahren kann, und dann, irgendwann macht's -Kluck- (oder 'Klick', je nachdem) und dann wundert man sich eben, wieso man sich vorher so einen abgebrochen hat.

In einem anderen Thread wurde die rekursive Implementierung der Fibbionacci-Zahlen als suizidal abgestempelt: Zu viele Aufrufe, zu lahm etc. Aber: bevor ich herangehe, um ein Problem optimal zu lösen, bin ich doch froh, es überhaupt in den Griff bekommen zu haben.

Rekursive Probleme, oder Probleme, die auf rekursiven Datenstrukturen beruhen, lassen sich am elegantesten nun mal mit rekursiven Ansätzen lösen. Deshalb ist es ja auch so wichtig, das man das 'gefressen' hat.

Gibt es hier im Forum Tutorials, die anhand einiger Beispiele die Rekursion hinreichend erklären? Könnte man nicht einige Übungsaufgaben bereitstellen?

Gausi - Fr 03.06.05 09:15

Ich will mal was zu dem Gerücht sagen, dass Rekursion allgemein lahm ist. Das stimmt nicht. Luckie hat da schon ein Beispiel genannt: Das Durchsuchen eines Verzeichnisses inklusiver aller Unterordner. Man untersucht alle Dateien in dem Verzeichnis, und durchsucht dann alle Unterordner in dem Verzeichnis mit demselben Verfahren. Eine iterative Lösung (sofern sie überhaupt existiert) kann nicht wesentlich schneller sein.

Dass die Rekursive Berechnung der Fibonacci-Zahlen so unpraktikabel ist, liegt daran, dass hier die Rekursion nicht einfach, sondern eher baumartig ist. Um Fib(5) zu berechnen, berechnet man

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

(A)Fib(4) 
   (a) Fib(3)
       (1) Fib(2)
           (i)  Fib(1)
           (ii) Fib(0)
       (2) Fib(1)
   (b) Fib(2)
       (1) Fib(1)
       (2) Fib(0)
(B)Fib(3)
   (a) Fib(2)
       (1) Fib(1)
       (2) Fib(0)
   (b) Fib(1)

Man sieht hier deutlich: Um die fünfte Fibonacci-Zahl zu berechnen, muss bereits dreimal die zweite berechnet werden. Für die nächste Zahl muss man das 5 mal tun, dann 8mal, 13mal, 21mal, usw. Kommt dir die Reihe bekannt vor?

Aber Rekursion an sich ist nicht ineffizient. Nur solche Arten wie man sie hier sieht.

Ein weiteres Problem, was man oft rekursiv löst, sind die Türme von Hanoi. Wenn man da das Prog mit einem Turm von 100 Scheiben laufen lässt, kann man als 15-jähriger auch schonmal darauf warten, bis der eigene Enkel Urgrossvater geworden ist. Und wenn man dann noch ein paar drauflegt, muss man dafür sorgen, dass der eigene Rechner das Universum ein paar mal überlebt. Aber das liegt dann nicht an der rekursiven Programmierung, sondern an dem Problem an sich. Die iterative Lösung ist nicht nur vollkommen unverständlich, sondern auch nicht schneller.

delfiphan - Fr 03.06.05 09:44

Ich muss Gausis Aussage etwas relativieren.

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

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;

Durchsuchen eines Verzeichnisses: Das Beispiel finde ich leider auch nicht so wirklich geschickt, denn dort ist der Bottleneck ja nicht der extra Funktionsaufruf sondern die Festplatte. Man muss natürlich schon ein Beispiel nehmen, wo das ganze geschwindigkeitskritisch ist.

Der Nachteil der Rekursion ist, dass sie viele Funktionsaufrufe generiert, was bei zeitkritischen Berechnungen eigentlich möglichst vermieden werden soll. Eine einfache Lösung ist eine Schleife mit einem Stack zu benützen. Das zeigt auch zugleich, dass man eine rekursive Berechnung immer mit Iteration+Stack umschreiben kann.

Wie gesagt: Die Frage, ob man etwas rekursiv oder iterativ löst hängt von der Aufgabenstellung ab; und meistens ist es ziemlich klar, welche man jetzt wählt...

Gausi - Fr 03.06.05 10:22

Also, wenn ich über 'Geschwindigkeit' und 'Laufzeiten' rede, dann meine ich das im Sinne der theoretischen Informatik, was in diesem Thread durchaus angebracht ist. Es geht mir hier nicht darum, ob eine Berechnung Compute(x:integer):integer; 5 Minuten oder 10 Minuten braucht. Es ist in meiner Argumentation auch völlig egal, dass Rekursion immer etwas langsamer ist, weil der Stack gefüllt werden muss, und der Funktionskopf abgearbeitet werden muss usw. Das ist mir alles völlig Wurscht.

Mir geht es ums Prinzip. Die Iterative Lösung von Fib(n) benötigt ungefähr n Rechenschritte. Die Rekursive Lösung, die ich vorgeschlagen habe, benötigt schätzungsweise knapp 2^n viele Schritte. Beim iterativen muss ich einen Schritt mehr machen, wenn ich Fib für eine um eins höhere Zahl berechnen will. Bei dem rekursiven Verfahren muss ich knapp doppelt soviel arbeiten. Und das ist schlecht. Ob da nun 'ein Rechenschritt' 1 Sekunde oder 2 oder 42 Sekunden braucht, spielt auch keine Rolle.
Das heißt: Wenn ich meinetwegen mit einem heutigen Rechner Fib(100) in einer Stunde rekursiv berechnen kann, dann brauche ich für Fib(101) zwei Stunden, für Fib(103) acht und für Fib(105) über einen Tag. Für Fib(200) bräuchte ich dann 2^100 Stunden. Solange gibbets die Welt nicht.
Wenn ich iterativ Fib(100.000) in einer Sekunde berechnen kann, dann kann ich Fib(100.001) in einer Sekunde und 0.01 Millisekunden oder so berechnen. Für Fib(200.000) benötige ich dann ca. zwei Sekunden. Das ist gut.

Beim durchsuchen der Festplatte passiert das bei einer rekursiven Lösung nicht. Wenn ich statt 100 Ordnern einen mehr habe, dann wird eben einer mehr durchsucht. Und nicht auf einmal doppelt oder dreimal soviele.
Und selbst wenn der Festplattenzugriff keine Zeit benötigen würde, würde ich die rekursive Variante trotzdem vorziehn. Wenn ich doppelte Geschwindigkeit möchte, dann kaufe ich mir eben nächstes Jahr einen neuen Rechner, und mein Programm läuft doppelt so schnell. (Wie gesagt, ich gehe die Dinge aus Sicht eines theor. Informatikers an, nicht aus Sicht eines Programmierers)

@delfiphan: Deine Lösung ist unpraktikabel. Sie berechnet zwar die Fibonaccizahlen bis maximal 100, aber du kannst damit nicht sagen, wie z.B. die 42.te Fibonaccizahl lautet. Und das möchte 'man'.

hansa - Fr 03.06.05 10:43

alzaimar hat folgendes geschrieben:

...Die Mechanik der Natur ist rekursiv...

Nun ja, das da ist jetzt aber sehr sehr weit ausgeholt. Wenn du jetzt gerade ein Kind machst :mrgreen: was ist daran rekursiv ? :shock: Das geht doch nur, weil Du schon da bist und bei der Rekursion geht das aber eben anders und umgekehrt rum. Und gerade deshalb ist es schwer verständlich, weil unnatürlich von der Denkweise her. Die Natur geht, wenn schon, dann in Richtung OOP, aber nicht Rekursion !

Luckies Beispiel ist das einzig vernünftige. Ich kann nicht wissen was am Ende herauskommt und fange deshalb oben in der Root an und wurschtele mich durch. Das macht Sinn und kann rekursiv am einfachsten gelöst werden. In meinem Bereich, also eher kaufmännisch mit DBs usw., hatte ich noch keine sinnvolle Verwendung für Rekursion. Allerdings schließe ich auch nicht aus, daß z.B. ein TreeView das intern auch mit Rekursion macht. Für reine eigene Programmteile habe ich sie allerdings noch nicht benötigt.

I.MacLeod - Sa 04.06.05 15:25

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!

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: http://www.linux-related.de/index.html?/coding/o-notation.htm

alzaimar - 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:

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.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!