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?

Oft ist er klar, wie man etwas programmieren muss. Meistens ist ein Problem eher rekursiver Natur oder nicht.
Wenn man eine Auswahl hat, dann nimmt man meistens Iteration für Geschwindigkeit und Rekursion für Eleganz.

Jemand ne Ahnung, wo ich gute theoretische Lektüre zum Thema Rekursion finden könnte? So die verschiedenen Arten, etc.

@alzaimar
Dann mach es einfach und gut, wo liegt dein Problem ?
(Viele Wege führen nach Rom) oder Übung macht den Meister usw.
Jeder fängt mal an.

Dumme Frage... Was heißt Rekursion ?

eine rekursion ist, wenn sich eine funktion selbst aufruft.

zum beipsiel:



wenn du jetzt

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

Jaja, was ist eigentlich Rekursion ? So einfach ist das nicht und bietet genug Spielraum für Mißverständnisse. Wer braucht denn das und wofür ? Ich habe es noch nicht zwingend gebraucht.

hansa hat folgendes geschrieben:

Ich habe es noch nicht zwingend gebraucht.

Noch nie einen Verzeichnisbaum durchsuchen mussen?

Ich hatte mal einen 5-fach geschachtelten Gruppenwechsel-Report mit diversen Zwischensummen. Gruppenwechsel waren auch innerhalb der Gruppen möglich. Ohne Rekursion hätte ich mir dabei einen Wolf programmiert. Es wäre sicher auch ohne Rekursion programmierbar gewesen, aber damals gab es noch keine dynamischen Arrays und wenn ich die ganzen Zwischenergebnisse in einer verketteten Liste verwalten müssen (mit den Report-Inhalten), wäre das erheblich komplizierter und aufwändiger geworden.

@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?

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

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.

Ein Link.
Dort wird es sehr ausführlich erklärt.

Ich muss Gausis Aussage etwas relativieren.

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


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

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'.

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 was ist daran rekursiv ? 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.

hansa hat folgendes geschrieben:

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 was ist daran rekursiv ?

Ganz einfach:
Mache(Kind) = Mache(alzaimar) + Mache(alzhaimars Weggefährtin)
Mache(alzaimar) = Mache(alzaimars Mutter) + Mache(alzaimars Vater)
(...)
Mache(Kain) = Mache(Adam) + Mache(Eva)
oder Mache(Abel) = Mache(Adam) + Mache(Eva)
Das wäre dann der Rekusionsabbruch.

Du siehst: Die Natur ist durch und durch rekursiv

Gausi: Du kannst ja in meiner rekursiven Lösung beim Funktionsaufruf noch einen Zähler mitgeben, der immer um eins erhöht wird. Das ist nicht das Problem. Wenn du Fibonacci in 2^n Schritten löst, dann bedeutet das, dass du dir ungefähr den schlechtestmöglichen Algorithmus ausgesucht hast. Das heisst noch lange nicht, dass Rekursionen schlecht sind, sondern bloss, dass du dir einen schlechten Algorithmus ausgedacht hast. Wenn du etwas iterativ in O(n) lösen kannst, kannst du es auch rekursiv in O(n). Und auch umgekehrt. Deswegen vergleiche ich nicht die Komplexität sondern die Laufzeit.

Ich bin ja auch der Meinung, dass Rekursion nicht im Allgemeinen schlecht ist. Und auch dein Verfahren lässt sich so modifizieren, dass es funktioniert. Aber meines ist näher an der Definition dran, denn Fib(n+2):=Fib(n)+Fib(n+1). Dein Verfahren ist im wesentlichen ja die iterative Lösung, nur rekursiv formuliert.

Aber schön zu sehen, dass hier noch jemand das O-Kalkül kennt

Gausi hat folgendes geschrieben:

...Aber schön zu sehen, dass hier noch jemand das O-Kalkül kennt

Jetzt wird es wieder OT, aber was ist O-Kalkül ?

Ein anders beispiel ist noch ein MainMenu: es hat untermenus und die haben wiederum untermenus: wie durchsucht man die am besten ? reskusiv oder nicht ?