Vereinfachtes Beispiel für Rekursion

...komplette Frage anzeigen

5 Antworten

Sagen wir, du willst ein Haus möblieren. Du bildest Teilaufgaben, zum Beispiel dass du jede Etage des Hauses möblierst. Dieses Teilproblem lässt sich unterteilen in die Probleme, alle Zimmer einer Etage zu möblieren. Du wendest das selbe Verfahren sozusagen auf die Teilprobleme an. In den einzelnen Zimmern könntest du beispielsweise einzelne Ecken möblieren, usw.

Das ist nicht "Rekursion", du beschreibst "Devide et Impera".

Rekursion (lat. "auf sich selbst beziehen") ist, dass du es in viele gleiche Teilprobleme zerteilst. Da sind zum Beispiel die "Türme von Hanoi" ein beispiel für.

1
@Flitztuete95

Rekursion (lat. "auf sich selbst beziehen") ist, dass du es in viele gleiche Teilprobleme zerteilst.

Was ist denn vom Typ her anders am Problem, eine Etage zu möblieren zu einem Haus zu möblieren. Das sind Probleme gleichen Typs. Man möbliert ein Haus indem man Etagen möbliert indem man Räume möbliert indem man Teile der Räume möbliert.
Der Prozess "Möblieren" wird rekursiv angewendet.

Das Hanoi-Beispiel ist abgelutscht und hat keine besondere praktische Relevanz, auch ist das darauf beruhende Sicherungsverfahren nichts "Greifbares".

2
@Flitztuete95

Bei "Teile und Herrsche" werden Teilprobleme gebildet, die nicht gleichen Typs sein müssen. Beispielsweise könnte das Problem "Garten aufhübschen" darin bestehen, ein Gartenhäuschen zu bauen, Büsche, Pflanzen und Bäume anzubauen und einen Teich anzulegen. Das Gartenhäuschen wird dann wieder in Teilprobleme zergliedert usw., bis eine ausreichende Tiefe erreicht worden ist.

2

Zweites ( 2.) Beispiel:

An einem Kirschbaum hängen richtig reife ( dunkle ) Kirschen und weniger reife ( hellere ) Kirschen.

Eine Person bekommt den Auftrag nur die dunkelsten Kirschen zu pflücken. Am Ende ist keine Kirsche mehr am Baum.

Warum? Die Person hat den Auftrag rekursiv ausgeführt.

Am Anfang verschwanden die dunkelsten im Korb. Danach wurde der Baum wieder begutachtet und es gab wieder dunklere und hellere. Der Auftrag lautete "die dunkelsten pflücken" . Nach Erledigung hat er die Kirschen am Baum erneut begutachtet. Es gab wieder dunklere und hellere ....

Irgendwann war die letzte verblieben Kirsche die dunkelste.

Hier war die Aufgabenstellung sicher falsch formuliert, die Aufgabe aber genau nach Aufgabenstellung ausgeführt. Die Frage ist nur, ist das im weitesten Sinne nicht doch Informatik?

Mir ist nicht ganz klar, was "fern ab der Informatik" heißen soll.

Daher hier ein praktisches Beispiel, das ein sehr wichtiger Bestandteil der Informatik ist (travelling salesman problem).

Für eine Gartenparty will man im Garten N elektrische Lampions an vorgegebenen Standorten mit Strom versorgen. In welcher Reihenfolge muss man die Lampions verbinden, um minimal viel Kabel zu verbrauchen.

Lösung:

Gegeben sei der letzte Lampion, der schon Strom hat, oder am Anfang die Steckdose. Man probiert der Reihe nach aus, welche der noch nicht verbundenen Lampions als Nächster angeschlossen wird. Bei jedem Versuch bleibt eine Menge mit einem Lampion weniger übrig, die noch angeschlossen werden müssen.

Hier setzt die Rekursion ein.

Beim trivialen Problem, bei dem nur noch ein Lampion angeschlossen werden muss, kann man die Lösung ohne Rekursion direkt angeben.

Achtung: dieses Problem ist sehr rechenaufwändig: auf einem modernen PC sind ca 14 Lampions möglich. Bei z.B. 50 Lampions wird man nie (in den nächsten paar Milliarden Jahren) die exakte Minimallösung kennen, und dies wird sich nach übereinstimmerender Meinung aller Mathematiker auch nie ändern. Dennoch lassen sich gute Näherungen in wenigen Sekunden berechnen (siehe z.B. die genetische Programmierung).

Es war einmal ein Mann, der hatte sieben Söhne. Die sieben Söhne sagten: Vater lies uns eine Geschichte vor. Da fing der Vater an,

Es war einmal ein Mann, der hatte sieben Söhne. Die sieben Söhne sagten: Vater lies uns eine Geschichte vor. Da fing der Vater an,

Es war einmal ein Mann, der hatte sieben Söhne. Die sieben Söhne sagten: Vater lies uns eine Geschichte vor. Da fing der Vater an,

Es war einmal ein Mann, der hatte sieben Söhne. Die sieben Söhne sagten: Vater lies uns eine Geschichte vor. Da fing der Vater an,

Es war einmal ein Mann, der hatte sieben Söhne. Die sieben Söhne sagten: Vater lies uns eine Geschichte vor. Da fing der Vater an,

.....

Hey,

leider mag Gutefrage irgendwie meine Antwort nicht, und weißt sie immer wieder zurück: Leider können wir Deinen Beitrag so nicht annehmen. Er enthält Wörter, die vulgär, beleidigend oder aus rechtlichen Gründen nicht zulässig sind. Bitte formuliere Deinen Beitrag neu.

(Es wird nicht einmal gesagt welches Wort Probleme macht.)

Ich habe Sie hier gepostet: https://gist.github.com/anonymous/f28f25c919fb12070616

Viele Grüße

Es gibt Wörter, die, auch wenn sie in einem ganz anderen Zusammenhang zu einer bestimmten Bedeutung stehen, von der GF-Software als "verboten" gewertet werde.

So durfte man den Namen Rab, wenn er mit 2 a geschrieben wurde hier nicht nennen, weil sich ein Stefan R das wohl verbeten hatte . Vielleicht findest du in deinem Text auch etwas, was an die Zeit vor 1945 erinnert.

0

Was möchtest Du wissen?