Rekursion -1

Einleitung 1

Der Prozess, bei dem sich eine Funktion selbst aufruft, wird Rekursion genannt und
Die entsprechende Funktion wird als rekursive Funktion bezeichnet.
Da Computerprogrammierung eine grundlegende Anwendung der Mathematik ist, also lass es
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 verschiedene Werte von x an diese Funktion ü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, eines
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ür
ein Basisfall wie n = 0 oder n = 1.
2.* Schritt der Annahme**: In diesem Schritt gehen wir davon aus, dass die gewünschte Aussage vorliegt
gilt für n = k.

1. Um den 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.

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 auf 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 erreichen
Abhängig von der Art des Problems.

Hinweis: Rekursion verwendet einen integrierten Stapel, der rekursive Aufrufe speichert. Daher die
Die Anzahl der rekursiven Aufrufe muss so gering wie möglich sein, um einen Speicherüberlauf zu vermeiden. Wenn
Die Anzahl der Rekursionsaufrufe überschreitet die maximal zulässige Menge, die
**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

1. Induktionsschritt: Berechnung der Fakultät einer Zahl n - F(n) Induktionshypothese: Wir haben bereits die Fakultät von n-1 - F(n-1)
erhalten
2. 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
}

1. Der Code ist immer 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 jetzt:

öffentliche statische int-Fakultät(int n){
if (n == 0) // Basisfall
return 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!