Rekursion -1

Einleitung 1

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:

public static int F(int x){

return (x * x + 4);
}

Jetzt können wir dieser Funktion verschiedene Werte von x übergeben und unsere Ausgabe erhalten

entsprechend.
Bevor wir mit der Rekursion fortfahren, versuchen wir, eine andere Mathematik zu verstehen
Konzept, bekannt als
Prinzip der Mathematischen Induktion (PMI).

Das Prinzip der mathematischen Induktion (PMI) ist eine Technik zum Beweis einer Aussage, a

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.

1. Um Schritt zu beweisen: Anhand der Ergebnisse des Annahmeschritts werden wir Folgendes beweisen: n = k + 1 gilt auch für die gewünschte Gleichung, wenn n = k wahr ist.

Zum Beispiel: Beweisen wir mithilfe des Prinzips der mathematischen Induktion, dass:

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.

Um zu beweisen: 1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2

Beweis:

Addieren von (k+1) sowohl zur linken als auch zur rechten Seite im in Schritt 2 erhaltenen Ergebnis:

1 + 2 + 3 + ... + (k+1) = (k*(k+1))/2 + (k+1)

Nehmen wir nun (k+1) gemeinsam von der rechten Seite:

1 + 2 + 3 + ... + (k+1) = (k+1)*((k + 2)/2)

Gemäß der Aussage, die wir zu beweisen versuchen:

1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
Somit bewiesen.

Funktionsweise der Rekursion

Wir können die Schritte des rekursiven Ansatzes definieren, indem wir die oben genannten drei zusammenfassen

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 Rekursion

Induktionsschritt: Berechnung der Fakultät einer Zahl n - F(n) Induktionshypothese: Wir haben bereits die Fakultät von n-1 - F(n-1)

erhalten
1. F(n) als F(n-1) ausdrücken: F(n)=n*F(n-1). So bekommen wir
public static int fact(int n){

int ans = fact(n-1); #Annahmeschritt

return ans * n; #Problemlösung aus dem Annahmeschritt
}

Der Code ist noch nicht vollständig. Der fehlende Teil ist der Basisfall. Jetzt werden wir es tun Führen Sie einen Probelauf durch, um den Fall zu finden, in dem die Rekursion gestoppt werden muss. Betrachten Sie n = 5:

Wie wir oben sehen können, kennen wir bereits die Antwort von n = 0, also 1. Das werden wir also tun

Behalten Sie dies als unseren Basisfall bei. Daher lautet der Code nun:

öffentliches statisches int faktorielles(int n){

if (n == 0) // Basisfall

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!