Rekursion
Swipe um das Menü anzuzeigen
Rekursion in der Programmierung bezeichnet die Technik, bei der eine Funktion sich selbst aufruft, um eine kleinere Instanz desselben Problems zu lösen. Sie ist eine leistungsfähige und elegante Methode, um Probleme zu lösen, die in kleinere Teilprobleme desselben Typs zerlegt werden können.
Rekursive Funktionen bestehen typischerweise aus zwei Komponenten:
-
Abbruchbedingung (Basisfall): Definiert die Abbruchbedingung für die rekursive Funktion. Wenn der Basisfall erreicht ist, stoppt die Funktion die weiteren Aufrufe und gibt einen bestimmten Wert zurück. Dies ist notwendig, um eine Endlosschleife zu verhindern.
-
Rekursiver Fall: Definiert die Logik zur Zerlegung des Problems in kleinere Teilprobleme und ruft die Funktion rekursiv mit reduzierten Eingaben auf. Der rekursive Fall ermöglicht es der Funktion, Fortschritte in Richtung Basisfall zu machen.
Die Fakultät einer Zahl n ist wie folgt definiert:
n! = n*(n-1)*(n-2)*..*2*1 = n*(n-1)!
main.cpp
12345678910111213141516171819#include <iostream> // Function to calculate factorial int factorial(int n) { // Base case: factorial of 0 or 1 is 1 if (n == 0 || n == 1) return 1; // Recursive case: multiply n with factorial of (n-1) std::cout << "Recursive Case: " << n << " * factorial(" << n - 1 << ")" << std::endl; return n * factorial(n - 1); } int main() { // Call the function std::cout << factorial(5) << std::endl; }
Basisfall: Der Basisfall tritt ein, wenn die Eingabe n gleich 0 oder 1 ist. In diesem Fall ist die Fakultät als 1 definiert. Der Basisfall stellt sicher, dass die Rekursion endet und verhindert eine unendliche Rekursion.
Rekursiver Fall: Der rekursive Fall ist die Logik zur Berechnung der Fakultät von n, wenn n größer als 1 ist. Dabei wird die Fakultätsfunktion rekursiv mit dem Argument n - 1 aufgerufen und das Ergebnis mit n multipliziert. Dadurch wird das Problem auf ein kleineres Teilproblem reduziert, indem die Fakultät einer kleineren Zahl berechnet wird.
Funktionsaufruf mit dem Argument 5. Hier ist der Schritt-für-Schritt-Prozess:
factorial(5)ruftfactorial(4)auf und multipliziert das Ergebnis mit 5.factorial(4)ruftfactorial(3)auf und multipliziert das Ergebnis mit 4.factorial(3)ruftfactorial(2)auf und multipliziert das Ergebnis mit 3.factorial(2)ruftfactorial(1)auf und multipliziert das Ergebnis mit 2.factorial(1)ist der Basisfall und gibt 1 zurück.- Die Multiplikation setzt sich in der Kette nach oben fort, was zur endgültigen Fakultät von
5führt, die120ergibt.
Danke für Ihr Feedback!
Fragen Sie AI
Fragen Sie AI
Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen
