Lernen Rekursion | Einige Fortgeschrittene Themen

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 leistungsstarke 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): Sie definiert die Abbruchbedingung für die rekursive Funktion. Wenn der Basisfall erreicht ist, stoppt die Funktion den Aufruf und gibt einen bestimmten Wert zurück. Dies ist notwendig, um eine unendliche Rekursion zu verhindern.
Rekursiver Fall: Er 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.

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

Hinweis

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

main.cpp


              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;
}

Hier folgt eine schrittweise Erklärung des obigen Codes:

Abbruchbedingung (Base Case): Die Abbruchbedingung tritt ein, wenn die Eingabe n gleich 0 oder 1 ist. In diesem Fall ist die Fakultät als 1 definiert. Die Abbruchbedingung stellt sicher, dass die Rekursion endet und verhindert eine unendliche Rekursion.

Rekursiver Fall: Der rekursive Fall beschreibt 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 Argument gleich 5. Hier ist der Ablauf Schritt für Schritt:

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 die Abbruchbedingung und gibt 1 zurück.
Die Multiplikation setzt sich in der Kette nach oben fort, was zur endgültigen Fakultät von 5 führt, die 120 ergibt.

War alles klar?

Danke für Ihr Feedback!

Abschnitt 4. Kapitel 3

Fragen Sie AI

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

Suggested prompts:

Can you show me the code for the recursive factorial function?

Can you explain how recursion works with another example?

What happens if there is no base case in a recursive function?

Awesome!

Completion rate improved to 5

Swipe um das Menü anzuzeigen