Rekursion

Rekursion in der Programmierung bezieht sich auf die Technik, bei der eine Funktion sich selbst aufruft, um eine kleinere Instanz desselben Problems zu lösen. Es ist ein mächtiger und eleganter Weg, Probleme zu lösen, die in kleinere Teilprobleme derselben Art zerlegt werden können.

Rekursive Funktionen bestehen typischerweise aus zwei Komponenten:

Basisfall: Er definiert die Abbruchbedingung für die rekursive Funktion. Sobald der Basisfall erreicht ist, hört die Funktion auf, sich selbst aufzurufen, und gibt einen spezifischen Wert zurück. Dies ist notwendig, um unendliche Rekursion zu vermeiden.
Rekursiver Fall: Er definiert die Logik zum Zerlegen des Problems in kleinere Teilprobleme und ruft die Funktion rekursiv mit den reduzierten Eingaben auf. Der rekursive Fall ermöglicht es der Funktion, Fortschritte in Richtung des Basisfalls zu machen.

Versuchen wir, die Fakultät einer Zahl mithilfe von Rekursion zu berechnen.

Hinweis

Die Fakultät einer Zahl n wird wie folgt definiert:
n! = n*(n-1)*(n-2)*..*2*1 = n*(n-1)!

main


              1234567891011121314151617181920
            
#include <iostream>

// Function to calculate factorial
int factorial(int n) {
    // Base case: factorial of 0 or 1 is 1
    if (n == 0 || n == 1) {
        std::cout << "Base Case: return 1" << std::endl;
        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;
}

Lasst uns eine schrittweise Erklärung des obigen Codes geben:

Basisfall: Der Basisfall tritt ein, wenn der Eingabewert n gleich 0 oder 1 ist. In diesem Fall ist die Fakultät als 1 definiert. Der Basisfall stellt sicher, dass die Rekursion terminiert und unendliche Rekursion verhindert wird.

Rekursiver Fall: Der rekursive Fall beschreibt die Logik zur Berechnung der Fakultät von n, wenn n größer als 1 ist. Hierbei wird die Fakultätsfunktion rekursiv mit n - 1 als Argument aufgerufen und mit n multipliziert. Dies reduziert das Problem auf ein kleineres Teilproblem, indem die Fakultät einer kleineren Zahl berechnet wird.

Die Funktion aufrufen mit dem Argument 5. Hier ist der schrittweise Prozess:

factorial(5) ruft factorial(4) auf und multipliziert das Ergebnis mit 5.
factorial(4) ruft factorial(3) auf und multipliziert das Ergebnis mit 4.
factorial(3) ruft factorial(2) auf und multipliziert das Ergebnis mit 3.
factorial(2) ruft factorial(1) auf und multipliziert das Ergebnis mit 2.
factorial(1) ist der Basisfall und gibt 1 zurück.
Die Multiplikation setzt die Kette fort, was zur endgültigen Fakultät von 5 führt, die 120 entspricht.

War alles klar?

Danke für Ihr Feedback!

Abschnitt 4. Kapitel 3