Video: Wissenschaftsdoku - Das Ende des Zufalls - Die Macht der Algorithmen (3SAT2015) 2024
Rekursion ist ein großes, beängstigendes Wort, das man oft über das Programmieren hört, besonders über die frustrierende Art von Programmierung, die sie an der Universität unterrichten. Obwohl es ein einfaches Konzept zu beschreiben ist, ist es wirklich ein Denker, wenn es darum geht zu verstehen, wie Rekursion funktioniert. Die meisten Leute akzeptieren es einfach und gehen weiter. Nicht hier!
Rekursion ist im Grunde der Prozess einer Funktion, die sich selbst aufruft. Zum Beispiel:
void funct (int x) {funct (x);}
In diesem Code-Block sehen Sie ein schreckliches Beispiel für eine rekursive Funktion, aber es dient hier der Veranschaulichung: Die Funktion Die Funktion () ruft sich auf. Das ist Rekursion. Was nun in diesem Beispiel passiert, ist im Grunde eine Endlosschleife, und dank eines technischen Etwas, das als Stackpointe r bezeichnet wird, stürzt der Computer schließlich ab. Aber es ist nur eine Illustration.
Für die Rekursion zur Arbeit muss die Funktion wie eine Schleife eine Bailout-Bedingung haben. Daher muss entweder der an die rekursive Funktion übergebene Wert oder sein Rückgabewert getestet werden. Hier ist ein besseres Beispiel für eine rekursive Funktion:
void recursion (int x) {if (x == 0) return; else {puts ("Boop!"); Rekursion (- x);}}
Die Funktion recursion () akzeptiert den Wert x . Wenn x gleich Null ist, bricht die Funktion ab. Andernfalls wird die Funktion erneut aufgerufen, aber der Wert von x wird reduziert. Der Dekrementpräfixoperator wird verwendet, so dass der Wert von x reduziert wird , bevor der Aufruf erfolgt.
Die sample recursion () Funktion spuckt den Text aus Boop! eine bestimmte Anzahl von Malen. Wenn also rekursion () mit dem Wert 10 aufgerufen wird, sehen Sie, dass dieser Text zehn Mal angezeigt wird.
Der wahnsinnige Teil der Rekursion besteht darin, dass sich die Funktion weiterhin selbst nennt, indem sie sich immer enger zusammenzieht, als wäre sie in einer Spirale. Im vorigen Beispiel wickelt die Bedingung x == 1 schließlich das verworrene Durcheinander ab und zieht sich zunehmend zurück, bis die Funktion abgeschlossen ist.
Der folgende Code zeigt ein vollständiges Programm, das die Beispielrekursionsfunktion () verwendet.
#include void rekursion (int x); int main () {Rekursion (10); return (0);} void rekursion (int x) {if (x == 0) return; else {puts ("Boop!"); Rekursion (- x);}}
Eine häufige Demonstration der Rekursion ist eine Fakultätsfunktion. Die Fakultät ist das Ergebnis der Multiplikation eines Wertes mit jeder seiner positiven ganzen Zahlen. Zum Beispiel:
4! = 4 × 3 × 2 × 1
Das Ergebnis dieser Fakultät ist 24. Der Computer kann diese Berechnung auch durchführen, indem er entweder eine Schleife implementiert oder eine rekursive Funktion erstellt.Hier ist eine solche Funktion:
int factorial (int x) {if (x == 1) return (x); else return (x * factorial (x-1));}
Wie bei den anderen rekursiven Funktionen enthält die Funktion factorial () eine Exit-Bedingung: x == 1. Andernfalls wird die Funktion erneut aufgerufen mit einem Wert kleiner als der aktuelle Wert von x . Aber die ganze Aktion findet mit den Rückgabewerten statt.
