Hauptunterschied – Rekursion vs. Iteration
Rekursion und Iteration können verwendet werden, um Programmierprobleme zu lösen. Der Ansatz zur Lösung des Problems durch Rekursion oder Iteration hängt von der Art und Weise ab, wie das Problem gelöst wird. Der Hauptunterschied zwischen Rekursion und Iteration besteht darin, dass Rekursion ein Mechanismus zum Aufrufen einer Funktion innerhalb derselben Funktion ist, während Iteration darin besteht, eine Reihe von Anweisungen wiederholt auszuführen, bis die angegebene Bedingung wahr ist. Rekursion und Iteration sind wichtige Techniken zum Entwickeln von Algorithmen und Erstellen von Softwareanwendungen.
Was ist Rekursion?
Wenn sich eine Funktion innerhalb der Funktion selbst aufruft, wird dies als Rekursion bezeichnet. Es gibt zwei Arten von Rekursion. Sie sind endliche Rekursion und unendliche Rekursion. Endliche Rekursion hat eine Beendigungsbedingung. Unendliche Rekursion hat keine Beendigungsbedingung.
Rekursion kann mit dem Programm zur Berechnung von Fakultäten erklärt werden.
n!=n(n-1)!, wenn n>0
n!=1, falls n=0;
Beziehen Sie sich auf den folgenden Code, um die Fakultät von 3(3!=321) zu berechnen.
intmain () {
int Wert=Fakultät (3);
printf(“Fakultät ist %d\n”, Wert);
return 0;
}
intfactorial (intn) {
if(n==0) {
return 1;
}
sonst {
return n Fakultät(n-1);
}
}
Wenn Fakultät (3) aufgerufen wird, ruft diese Funktion Fakultät (2) auf. Wenn Fakultät (2) aufgerufen wird, ruft diese Funktion Fakultät (1) auf. Dann ruft Fakultät (1) Fakultät (0) auf. Fakultät (0) gibt 1 zurück. Im obigen Programm ist die Bedingung n==0 im „Wenn-Block“die Grundbedingung. Entsprechend wird die Fakultätsfunktion immer wieder aufgerufen.
Rekursive Funktionen beziehen sich auf den Stack. In C kann das Hauptprogramm viele Funktionen haben. main() ist also die aufrufende Funktion, und die Funktion, die vom Hauptprogramm aufgerufen wird, ist die aufgerufene Funktion. Wenn die Funktion aufgerufen wird, wird die Steuerung an die aufgerufene Funktion übergeben. Nachdem die Ausführung der Funktion abgeschlossen ist, wird die Steuerung an main zurückgegeben. Dann geht das Hauptprogramm weiter. Es erstellt also einen Aktivierungsdatensatz oder einen Stapelrahmen, um die Ausführung fortzusetzen.
Abbildung 01: Rekursion
Im obigen Programm wird beim Aufrufen von Fakultät (3) von main ein Aktivierungsdatensatz im Aufrufstapel erstellt. Dann wird der faktorielle (2) Stapelrahmen oben auf dem Stapel erstellt und so weiter. Der Aktivierungsdatensatz enthält Informationen über lokale Variablen usw. Jedes Mal, wenn die Funktion aufgerufen wird, wird ein neuer Satz lokaler Variablen oben auf dem Stapel erstellt. Diese Stapelrahmen können die Geschwindigkeit verlangsamen. Ebenso ruft sich bei der Rekursion eine Funktion selbst auf. Die Zeitkomplexität für eine rekursive Funktion ergibt sich aus der Anzahl der Aufrufe der Funktion. Die Zeitkomplexität für einen Funktionsaufruf ist O(1). Für n rekursive Aufrufe ist die Zeitkomplexität O(n).
Was ist Iteration?
Iteration ist ein Block von Anweisungen, der immer wieder wiederholt wird, bis die gegebene Bedingung wahr ist. Die Iteration kann mit „for-Schleife“, „do-while-Schleife“oder „while-Schleife“erreicht werden. Die „for-Schleife“-Syntax lautet wie folgt.
für (Initialisierung; Bedingung; Modifizierung) {
// Anweisungen;
}
Abbildung 02: „For-Loop-Flussdiagramm“
Initialisierungsschritt wird zuerst ausgeführt. Dieser Schritt besteht darin, Schleifensteuervariablen zu deklarieren und zu initialisieren. Wenn die Bedingung wahr ist, werden die Anweisungen in den geschweiften Klammern ausgeführt. Diese Anweisungen werden ausgeführt, bis die Bedingung wahr ist. Wenn die Bedingung falsch ist, geht die Steuerung zur nächsten Anweisung nach der „for-Schleife“. Nach dem Ausführen der Anweisungen innerhalb der Schleife geht die Steuerung zum Änderungsabschnitt. Es dient zum Aktualisieren der Schleifensteuervariablen. Dann wird die Bedingung erneut überprüft. Wenn die Bedingung wahr ist, werden die Anweisungen in den geschweiften Klammern ausgeführt. Auf diese Weise wird die „for-Schleife“durchlaufen.
In einer „while-Schleife“werden die Anweisungen innerhalb der Schleife ausgeführt, bis die Bedingung wahr ist.
während (Bedingung){
//Anweisungen
}
In der „do-while“-Schleife wird die Bedingung am Ende der Schleife geprüft. Die Schleife wird also mindestens einmal ausgeführt.
tun{
//Anweisungen
} while(condition)
Programm zum Finden der Fakultät von 3 (3!) mit Iteration („for-Schleife“) lautet wie folgt.
int main(){
intn=3, Fakultät=1;
inti;
for(i=1; i<=n; i++){
factorial=Fakultäti;
}
printf(“Fakultät ist %d\n”, Fakultät);
return 0;
}
Was sind die Ähnlichkeiten zwischen Rekursion und Iteration?
- Beides sind Techniken, um ein Problem zu lösen.
- Die Aufgabe kann rekursiv oder iterativ gelöst werden.
Was ist der Unterschied zwischen Rekursion und Iteration?
Rekursion vs. Iteration |
|
| Rekursion ist eine Methode zum Aufrufen einer Funktion innerhalb derselben Funktion. | Iteration ist ein Anweisungsblock, der wiederholt wird, bis die gegebene Bedingung wahr ist. |
| Raumkomplexität | |
| Die Raumkomplexität rekursiver Programme ist höher als bei Iterationen. | Raumkomplexität ist in Iterationen geringer. |
| Geschwindigkeit | |
| Rekursionsausführung ist langsam. | Normalerweise ist Iteration schneller als Rekursion. |
| Zustand | |
| Wenn es keine Abbruchbedingung gibt, kann es zu einer unendlichen Rekursion kommen. | Wenn die Bedingung nie falsch wird, wird es eine unendliche Iteration sein. |
| Stapel | |
| Bei der Rekursion wird der Stack verwendet, um lokale Variablen zu speichern, wenn die Funktion aufgerufen wird. | Bei einer Iteration wird der Stack nicht verwendet. |
| Codelesbarkeit | |
| Ein rekursives Programm ist besser lesbar. | Das iterative Programm ist schwieriger zu lesen als ein rekursives Programm. |
Zusammenfassung – Rekursion vs. Iteration
Dieser Artikel behandelt den Unterschied zwischen Rekursion und Iteration. Beide können verwendet werden, um Programmierprobleme zu lösen. Der Unterschied zwischen Rekursion und Iteration besteht darin, dass Rekursion ein Mechanismus zum Aufrufen einer Funktion innerhalb derselben Funktion und Iteration ist, um eine Reihe von Anweisungen wiederholt auszuführen, bis die angegebene Bedingung wahr ist. Wenn ein Problem rekursiv gelöst werden kann, kann es auch durch Iterationen gelöst werden.
Laden Sie die PDF-Version von Rekursion vs. Iteration herunter
Sie können die PDF-Version dieses Artikels herunterladen und gemäß Zitationshinweis für Offline-Zwecke verwenden. Bitte laden Sie die PDF-Version hier herunter. Unterschied zwischen Rekursion und Iteration
