Rekursion

Rekursion

> LeekScript-Tutorial

Voraussetzungen:

----

Rekursion ist allgemein gesagt die Fähigkeit eines Objekts, auf sich selbst zu verweisen. In der realen Welt zeigt sich dies am deutlichsten in Fraktalen sowie wenn zwei Spiegel einander gegenüber liegen. Wir finden diesen Begriff auch in Sätzen der Art: "Ich träume, dass ich träume, dass ich träume." oder "Ich denke, dass ich schreibe, dass ich träume, dass ich denke, dass ich schreibe..." usw In der Programmierung manifestiert sich dies meist mit Funktionen, die sich selbst aufrufen:

Funktion Schleife () { Schleife(); }

Die obige Funktion ist die einfachste rekursive Funktion, die es gibt. Wenn es gerufen wird, tut es nichts anderes, als sich selbst anzurufen. Dies ist dasselbe wie die Verwendung einer Endlosschleife (z. B. while(true);). Wir werden diese Funktion als Grundgerüst für alle unsere zukünftigen rekursiven Funktionen verwenden.

Rekursion

Rekursion ist analog zur Dekonstruktion. Es wird hauptsächlich in Algorithmen vom Typ „Divide and Conquer“ gefunden. Um unser Problem zu lösen, beginnen wir damit, es in einfacher zu lösende Unterprobleme zu unterteilen, wir wiederholen den Prozess, bis wir ein Problem finden, von dem wir wissen, wie es direkt gelöst werden kann, und von dort aus lösen wir die höheren Probleme, indem wir unsere vorherigen kombinieren Lösungen.

Summe von 0 bis n setzen

Wir wollen eine Funktion definieren, die eine Ganzzahl n als Parameter nimmt und die Summe von 0 bis n zurückgibt (zB 0 + 1 + ... + n). Wenn wir unser Grundgerüst nehmen, können wir mit der folgenden Funktion beginnen:

Funktion SummeN(n) { summeN(?); zurückkehren?; }

Im Moment haben wir folgende Informationen:

Wenn Sie rekursiv arbeiten, ist es immer eine gute Idee, mit der Stoppbedingung zu beginnen. Im Fall der Rekursion wollen wir aufhören, Unterprobleme zu erzeugen, wenn wir etwas gefunden haben, das wir lösen können. In diesem Fall ist die Summe von „0“ zu „0“ etwas, das wir zu lösen wissen. 0 ist also unser Basisfall, wir können direkt die entsprechende Summe zurückgeben.

Funktion SummeN(n) { Wenn (n === 0) {Rückgabe 0; } Sonst {SumN(?); zurückkehren?; } }

Wir müssen jetzt herausfinden, wie wir den Basisfall erreichen. Wir könnten n von sich selbst subtrahieren, aber in diesem Fall könnten wir die ganzen Zahlen zwischen 0 und n nicht summieren, wir hätten nur 0 und n zur Verfügung. Wir müssen daher ein Unterproblem erstellen, das eine Summe mit einem n näher an unserem Basisfall lösen kann.

Funktion SummeN(n) { Wenn (n === 0) {Rückgabe 0; } sonst { sumN (n - 1); zurückkehren?; } }

Wir brauchen jetzt nur noch die Summe zu machen, die zu Beginn von uns verlangt wurde. Hier ist die Summe von 0 bis n auch die Summe der Summe von 0 bis n - 1 und n.

Funktion SummeN(n) { Wenn (n === 0) {Rückgabe 0; } Sonst {Rückgabe n + sumN(n - 1); } }

Mit einem Dreier:

Funktion SummeN(n) { Rückgabe n === 0? 0 : n + summeN(n - 1); }

Fühlen Sie sich frei, den Code in Ihrem Leekwars-Editor auszuprobieren. Vielleicht entdecken Sie das Hauptproblem bei der Rekursion. Sie können die Ausführung (auf einfache Weise) auch auf [dieser Website] (http://www.pythontutor.com/visualize.html#mode=display) visualisieren.

Corecursion

/!\ Zu wiederholender Abschnitt, was gezeigt wird, ist hauptsächlich Schwanzrekursion. Für mehrere Filialen ungeeignet. /!\ Corecursion ist analog zur Konstruktion. Anders als bei der Rekursion, bei der wir versuchen, von unserem Hauptproblem zu einem Basisfall zu gelangen, beginnen wir bei der Co-Rekursion direkt mit unserem Basisfall und bewegen uns auf die Lösung des Hauptproblems zu.

Wechselseitige Rekursion

Wir haben die wechselseitige Rekursion bereits mit Spiegeln und Sätzen behandelt. Bei der Programmierung mit Funktionen bedeutet dies, dass zwei oder mehr Funktionen sich gegenseitig aufrufen. Nachfolgend stellen wir den einfachsten Fall gegenseitiger Rekursion vor:

Funktion MutualLoop() { Gegenseitiger Helfer(); }

Funktion mut