Was ist Rekursion | möglichst simpel erklärt?
Kann mir bitte jemand den Begriff "Rekursion" erklären? Ich raff das irgendwie nicht... Und bitte keinen Wikipedia link, ich brauch ne erklärung von jemandem, der auch normale wörter nutzt^^
6 Antworten
Ganz Allgemein:
Immer wenn ein Problem in ein Teilproblem zerlegt werden kann, welches wieder "genauso ausieht" wie das ursprüngliche, aber auf einer kleineren Datenmenge (oder kleinerem Wert) operiert. Und es eine Abbruchbedingung gibt, bei dem man mit der Rekursion aufhört.
Ein paar klassische Beispiele:
Beispiel I) Fakultät
Fakultät ist eine mathematische Funktion, die man oft (Statistik, Wahrscheinlichkeitsrechnung, Kombinatorik etc.) braucht.
Die Fakultät von einer ganzen Zahl n (geschrieben als "n!") ist definiert als:
1 * 2 * 3 * 4 * ... * (n-2) * (n-1) * n
also das Produkt aller Zahlen von 1 bis n.
Um n! auszurechnen, kann man sich sagen:
1) mhm; nehmen wir mal an, ich wüsste, was (n-1)! ist.
2) dann wäre es leicht, n! auszurechnen (einfach mit n multiplizieren)
3) ok, wie kriege ich (n-1)!
4) genauso: nehmen wir mal an, ich wüsste was (n-2)! ist
usw.
wann muss ich aufhören?
bei 1!
Da liefere ich den Wert 1.
Also schreibe ich eine Funktion:
function fakultät(n) {
if (n == 1)
return 1;
else
return fakultät(n-1) * n;
}
Beispiel II) Bäume
Suchmäume sind eine klassiche Datenstruktur in der Informatik. Er besteht aus Knoten. Diese halten ein Datum (z.B. die Telefonnummer und einen Namen) sowie möglicherweise 1-2 Referenzen zu Unterbäumen, die ihrerseits wieder Knoten.
(https://de.wikipedia.org/wiki/Bin%C3%A4rbaum)
Die Unterknoten sind so angeordnet, daß alle kleineren Namen links, alle größeren im rechten Unterbaum sind.
Um einen sortierten Baum nach einem Namen zu durchsuchen, kommt man im günstigsten Fall mit log(n) Vergleichen aus (man muss also nicht alle Blätter durchsuchen, um z.B. eine Telefonnummer zu finden, sondern nur log(n). Das ist ein Riesenunterschied, wenn man z.B. 100000 Adressen oft zu durchsuchen hat...
Zum Suchen eines Namens im Baum sagt man sich:
1) mhm; zuerst schau ich, ob der zu suchende Name gleich ist dem im Knoten ist
2) wenn nicht gibt es zwei Möglichkeiten:
2a) wenn der zu suchende Name kleiner als der im Knoten ist, durchsuche ich den linken Unterbaum
2b) ansonsten durchsuche den rechten Teilbaum
Der Algorithmus ist:
function findeName(String name, Baum b) {
if (b == NULL) {
return NULL; // nichts gefunden
}
if ( name = nameImKnoten(b) ) {
return b;
} else {
if ( name < nameImKnoten(b) )
return findeName(name, linkerKnoten(b));
} else {
return findeName(name, rechterKnoten(b));
}
}
}
Auch hier wieder die Rekursion (suche im Teilbaum) und Abbruchbedingung (Name gefunden bzw. kein Unterbaum)
Beispiel III) Compiler
Der Sprachübersetzer (Compiler) liest ja ein Programm ein, und prüft die Korrektheit. Z.B. eine Anweisung:
statement ::= <ifStatement> | <whileStatement> | .... | <returnStatement>
ifStatement ::= "if" "(" <bedingung> ")" <statement> [ "else" <statement> ]
Im Compiler gibt es eine funktion "parseStatement", die eine Anweisung analysiert:
function parseStatement() {
if (nextWord = "if") {
return parseIfStatement();
} else if (nextWord = "while") {
return parseWhileStatement();
} else
... usw ...
}
function parseIfStatement() {
readNextWord();
if (nextWord != "(") error();
readNextWord();
parseBedingung();
if (nextWord != ")") error();
parseStatement();
if (nextWord = "else") {
readNextWord();
parseStatement();
}
}
Hier haben wir eine indirekte Rekursion
"parseStatement() -> parseIfStatement() -> parseStatement()"
Übrigens:
oft kann man Rekursion durch Schleifen ersetzen. Z.B. die Fakultät oben wird normalerweise mittels Schleife berechnet. Bei Bäumen und beim Parsen ist das aber nicht immer so leicht möglich (es geht schon, aber der Code wird dadurch unübersichtlicher).
So, jetzt habe ich mir Mühe gemacht, und hoffe jeder versteht es jetzt!
Ja, ich weiß was du meinst:) Ich versuche es mal mit eigenen Worten. Aber verspreche dir nicht das ich mich wirklich geschickt anstelle...
Also bei der Rekursion startet eine Funktion eine weitere Instanz seiner selbst, wenn bei der Prüfung ob das Ergebnis denn Zielvorgaben entspricht ein false zurückgegeben wird (also unwahr). Die nächste Instanz übernimmt dann denn geprüften Wert über denn Rückgabewert ihres Vorgängers und versucht eine genaueren Wert (man kann auch sagen eine genauere Definition seiner selbst) zu ermitteln der dann ebenfalls von der func geprüft wird.
Wenn die Prüfung dann positiv ist, bauen dann sich die Instanzen der selben Funktion quasi rückwärts ab wobei der Wert, also das Endergebnis an immer die Vorgänger-Instanz zugeworfen wird.
Die rekursive Lösung von Türme von Hanoi ist ein gutes Beispiel für einen solchen Algorithmus.
Stimmt. Das hängt wohl damit zusammen das ich solche Dinge bildlich erfasse und dann schreibe was ich sehe, ungeachtet wie es ein Computer sehen würde.
Fünf-Dimensionales bildliches Denken überlastet meinen Positronische Matrix, fürchte ich^^
In der Wiki steht das der richtige Ausdruck "Inkarnation" lautet.
stimmt fast.
Die RAM Bereiche für die Argumente sowie lokale Variablen werden pro Aufruf "instanziiert".
Typischerweise, aber nicht immer, auf einem Stack.
Das nennt man Callframe, Continuation oder eben Stackframe.
Die Funktion wird tatsächlich konzeptionell nur einmal "instanziiert".
Wobei in modernen Systemen (Smalltalk, Java, C#) auch das nicht mehr unbedingt stimmt, denn moderne Systeme rekompilieren Funktionen dynamisch, um z.B. besser optimierten Code, angepasst an konkrete Receiver oder Argumenttypen, zu erzeugen.
Dies nennt man "dynamische Recompilierung" oder auch neudeutsch "hot spot compilation".
Eine Rekursion kannst du dir am besten so vorstellen:
Eine Person liest ein Buch, in welchem eine andere Person einen Film schaut, in welchem wiederum eine andere Person Zeitung liest usw.
Der Film Inception ist z.B. ein gutes Beispiel dafür: Ein Traum in einem Traum in einem Traum usw.
Das ist jetzt wirklich nur eine sehr vereinfachte Darstellung. Wenn es dann im die Informatik geht, dann gibt es z.B. rekursive Methoden, die sich immer wieder selbst aufrufen, bis eine Abbruchbedingung (Diese legt man vorher fest) eintritt.
Nimm einen Zettel zur Hand,
Schreib drauf "Bitte die Anweisung auf der Rückseite dieses Zettels ausführen".
Dreh ihn um und schreib drauf "Bitte die Anweisung auf der Rückseite dieses Zettels ausführen".
Dann lies die Anweisung, die auf dem Zettel steht und führe sie aus.
Das ist Rekursion. Sind die Wörter normal genug?
Na toll, jetzt habe ich die letzten 12 Stunden ununterbrochen genau das gemacht, was du gesagt hast, und dann gab es einen Stapelüberlauf (vor Müdigkeit zusammen gebrochen).
Ich konnte irgendwie gar nicht mehr damit aufhören ... das nächste mal baue doch bitte eine Abbruchbedingung ein, wenn du solche gefährlichen Antworten gibst! :)
baue doch bitte eine Abbruchbedingung ein
Hab ich doch.
Indirekt.
Die Abbruchbedingung ist implizit in der technischen Umsetzung des Algorithmus eingebaut.
"Wenn du die Anweisung vor Erschöpfung nicht mehr lesen kannst, brich erschöpft zusammen und schlepp dich mit deinen letzten Kräften ins Bett".
Das extra hinschreiben wäre übrigens kontraproduktiv gewesen. Der erschöpfte Proband hätte sie ja eh nicht mehr lesen können.
Lieber einen Stapelüberlauf als einen Syntax Error.
Dein "Betriebssystem" hat doch für Stapelüberlauf bereits eine gut getestete Routine implementiert.
Ein vor Erschöpfung zusammen gebrochenes TeeTier ist mir immer noch lieber als ein amoklaufendes ;-)
Als Rekursion bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich selbst zu definieren. Wenn man mehrere Funktionen durch wechselseitige Verwendung voneinander definiert, spricht man von wechselseitiger Rekursion.
Klasse antwort Chippo, aber du redest von "Instantz" einer funktion. Werden Funktionen etwa instanziert? Also meine Funktion rattert durch und die abbruchbedingung trifft nicht zu, also übergibt sie benötigte werte an sich selbst und durchläuft sichselbst mit (hoffentlich :P) neuen pararmetern. Das so lange, bis alles meine Abbruchbedingung erfüllt ist. Werden Funktionen also tatsächlich pro Durchlauf im RAM "instanziert"? Ziemlich sicher nicht. Zum einen ist der Begriff "instanz" nur auf Klassen und ihre Objekte zu beziehen. Funktionen werden immer nur 1 mal pro Klasse deklariert (reservierung im RAM) und initialisert (gefüllt mit 1 und 0 :P)! Höchstens ihre lokale Variablen werden erneut deklariert. Die gleiche Bereich im RAM, in dem die Funktion definiert ist wird durchlaufen, es werden also keine neuen Bereiche im RAM reserviert. es werden jedeglich nur andere Werte an die SELBE "Insatanz", wie du es nanntest, übergeben.
Aber ja, der Prozess der Rekursion hast du sehr gut ausgedrückt^^
Wollte nur korrigieren dass keine Funktionen instanziert werden :D