Rekursive Fakultät

Teil des Abschnitts Logik & Ablauf der C++-Journey von Coddy — Lektion 46 von 56.

Die Fakultät einer Zahl ist ein perfektes Beispiel, um Rekursion in Aktion zu demonstrieren. Die Fakultät von n (geschrieben als n!) ist das Produkt aller positiven ganzen Zahlen von 1 bis n. Zum Beispiel ist 5! = 5 × 4 × 3 × 2 × 1 = 120.

Was die Fakultät ideal für die Rekursion macht, ist, dass sie durch sich selbst definiert werden kann: n! = n × (n-1)!. Das bedeutet, um 5! zu berechnen, multipliziert man 5 mit 4!, und um 4! zu berechnen, multipliziert man 4 mit 3!, und so weiter.

So sieht eine rekursive Fakultätsfunktion aus:

int factorial(int n) {
    if (n <= 1) {           // Basisfall: 0! und 1! sind beide gleich 1
        return 1;
    }
    
    return n * factorial(n - 1);  // Rekursionsschritt: n! = n × (n-1)!
}

Der Basisfall stoppt die Rekursion, wenn n den Wert 1 oder 0 erreicht, und gibt 1 zurück. Der rekursive Schritt multipliziert die aktuelle Zahl mit der Fakultät der nächstkleineren Zahl. Wenn Sie factorial(4) aufrufen, berechnet es 4 × 3 × 2 × 1, indem es aufeinanderfolgende Aufrufe tätigt, bis es den Basisfall erreicht, und dann alle Ergebnisse multipliziert, während die Aufrufe zurückkehren.

Aufgabe

Einfach

Erstellen Sie ein Programm, das eine rekursive Fakultätsfunktion implementiert und diese verwendet, um Fakultäten für verschiedene Eingabewerte zu berechnen. Diese Herausforderung testet Ihr Verständnis der Funktionsweise von Rekursion, indem eine Funktion sich selbst mit geänderten Parametern aufruft, bis sie einen Basisfall erreicht.

Die folgende Eingabe wird bereitgestellt:

Eine Ganzzahl n, die die Zahl darstellt, für die die Fakultät berechnet werden soll

Ihr Programm sollte:

Eine rekursive Funktion namens factorial erstellen, die einen Ganzzahl-Parameter entgegennimmt und eine Ganzzahl zurückgibt
Die Funktion sollte den Basisfall implementieren: Wenn n kleiner oder gleich 1 ist, geben Sie 1 zurück
Die Funktion sollte den rekursiven Schritt implementieren: Geben Sie n multipliziert mit der Fakultät von n-1 zurück
In der Hauptfunktion den Eingabewert einlesen
Die Funktion factorial mit dem Eingabewert aufrufen
Das Ergebnis im angegebenen Format ausgeben

Verwenden Sie das folgende exakte Ausgabeformat:

Factorial of [n] is [result]

Denken Sie daran, dass die Fakultätsfunktion sich bei jedem Aufruf mit einem kleineren Wert selbst aufrufen muss, um sich mit jedem rekursiven Aufruf dem Basisfall zu nähern. Der Basisfall verhindert eine unendliche Rekursion, indem er stoppt, wenn n 1 oder 0 erreicht. Der rekursive Schritt multipliziert die aktuelle Zahl mit der Fakultät der nächstkleineren Zahl und baut so das Endergebnis auf, während die Funktionsaufrufe ihre Werte zurückgeben.

Spickzettel

Die Fakultät von n (n!) ist das Produkt aller positiven ganzen Zahlen von 1 bis n. Sie kann rekursiv definiert werden als: n! = n × (n-1)!

Rekursive Fakultätsfunktion:

int factorial(int n) {
    if (n <= 1) {           // Basisfall: 0! und 1! sind beide gleich 1
        return 1;
    }
    
    return n * factorial(n - 1);  // Rekursionsschritt: n! = n × (n-1)!
}

Der Basisfall stoppt die Rekursion, wenn n 1 oder 0 erreicht. Der Rekursionsschritt multipliziert die aktuelle Zahl mit der Fakultät der nächstkleineren Zahl.

Probier es selbst

#include <iostream>
using namespace std;

// TODO: Schreiben Sie hier Ihre Fakultätsfunktion

int main() {
    // Eingabe lesen
    int n;
    cin >> n;
    
    // TODO: Rufen Sie die Fakultätsfunktion auf und speichern Sie das Ergebnis
    
    // Ergebnis ausgeben
    cout << "Factorial of " << n << " is " << result << endl;
    
    return 0;
}

Teste dich selbst

Diese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.

Alle Lektionen in Logik & Ablauf

3Projekt: Aufgabenlisten-Tool

Projektübersicht Eine Aufgabe hinzufügen

Aufgaben anzeigen

Eine Aufgabe entfernen

Das Tool fertigstellen

6Sets (Eindeutige Elemente)

Einführung in std::set Set erstellen & Elemente hinzufügen Auf Elemente prüfen Elemente entfernen Über ein Set iterieren Zusammenfassung – Eindeutige Zahlen

9Abschlussherausforderungen

Vektor-Datenfilterung Map-Wertsuche Pointer und dynamische Arrays