Der Prozess, bei dem sich eine Funktion selbst aufruft, wird als Rekursion bezeichnet Die entsprechende Funktion wird als
rekursive Funktionbezeichnet.Da Computerprogrammierung eine grundlegende Anwendung der Mathematik ist, also lasst es sein
Wir versuchen zunächst, die mathematischen Gründe für die Rekursion zu verstehen.
Im Allgemeinen ist uns allen das Konzept der Funktionen bekannt. Kurz gesagt, Funktionen sind
mathematische Gleichungen, die bei Bereitstellung einer Eingabe eine Ausgabe erzeugen. Zum Beispiel:
Angenommen, die Funktion F(x) ist eine Funktion definiert durch: F(x) = x^2 + 4
Wir können den Java-Code für diese Funktion wie folgt schreiben:
return (x * x + 4);
}
entsprechend.
Bevor wir mit der Rekursion fortfahren, versuchen wir, eine andere Mathematik zu verstehen
Konzept, bekannt als
Prinzip der Mathematischen Induktion (PMI).
Formel oder ein Satz, der über eine Menge natürlicher Zahlen aufgestellt wird. Es hat das
folgenden drei Schritten:
1.** Schritt des Trivialfalls*
: In diesem Schritt beweisen wir die gewünschte Aussage fürein Basisfall wie n = 0 oder n = 1.
2.
* Schritt der Annahme**: In diesem Schritt gehen wir davon aus, dass die gewünschte Aussage vorliegtgilt für n = k.
S(N): 1 + 2 + 3 + ... + N = (N * (N + 1))/2
(Die Summe der ersten N natürlichen Zahlen)
Beweis:
Schritt 1: Für N = 1 ist S(1) = 1 wahr.
Schritt 2: Nehmen Sie an, dass die gegebene Aussage für N = k wahr ist, d. h.
1 + 2 + 3 + .... + k = (k * (k + 1))/2
Schritt 3: Beweisen wir die Aussage für N = k + 1 mit Schritt 2.
Beweis:
1 + 2 + 3 + ... + (k+1) = (k*(k+1))/2 + (k+1)
1 + 2 + 3 + ... + (k+1) = (k+1)*((k + 2)/2)
1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
Somit bewiesen.
Schritte:
● Basisfall: Eine rekursive Funktion muss eine Abschlussbedingung haben, bei der
Der Prozess ruft sich nicht mehr selbst auf. Ein solcher Fall wird als Basisfall bezeichnet. Ohne einen Basisfall ruft es sich ständig selbst auf und bleibt in einem
stecken Endlosschleife. Bald wird die Rekursionstiefe* überschritten und es wird ausgelöst
ein Fehler.
● Rekursiver Aufruf: Die rekursive Funktion ruft sich selbst in einer kleineren Version auf
des Hauptproblems. Wir müssen beim Schreiben dieses Schritts vorsichtig sein
Es ist wichtig, richtig herauszufinden, was Ihr kleineres Problem ist.
● Kleine Berechnung: Im Allgemeinen führen wir in jeder Rekursion einen Berechnungsschritt durch
Anruf. Wir können diesen Berechnungsschritt vor oder nach dem rekursiven Aufruf ausführen
Abhängig von der Art des Problems.
Hinweis: Rekursion verwendet einen integrierten Stapel, der rekursive Aufrufe speichert. Daher dieDie Anzahl der rekursiven Aufrufe muss so gering wie möglich sein, um einen Speicherüberlauf zu vermeiden. Wenn
Die Anzahl der Rekursionsaufrufe überschreitet den maximal zulässigen Betrag, den
**Rekursionstiefe
** wird überschritten.Sehen wir uns nun an, wie man mit Rekursion einige häufig auftretende Probleme löst
Problemstellung – Fakultät einer Zahl finden
Ansatz: Die drei Schritte des PMI herausfinden und diese dann mithilfe von
in Beziehung setzen Rekursionreturn ans * n; #Problemlösung aus dem Annahmeschritt
}
Wie wir oben sehen können, kennen wir bereits die Antwort von n = 0, also 1. Das werden wir also tun
öffentliches statisches int faktorielles(int n){
Rückgabe 1;
sonst
return n*factorial(n-1); // rekursiver Fall
}
Das obige ist der detaillierte Inhalt vonRekursion -1. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!