Rekurencyjny silnia

Część sekcji Logika i przepływ programu ścieżki C++ w Coddy. Lekcja 46 z 56.

Silnia liczby to doskonały przykład ilustrujący działanie rekurencji. Silnia liczby n (zapisywana jako n!) to iloczyn wszystkich dodatnich liczb całkowitych od 1 do n. Na przykład 5! = 5 × 4 × 3 × 2 × 1 = 120.

Silnia doskonale nadaje się do rekurencji, ponieważ można ją zdefiniować za jej pomocą: n! = n × (n-1)!. Oznacza to, że aby obliczyć 5!, mnożysz 5 przez 4!, a aby obliczyć 4!, mnożysz 4 przez 3! i tak dalej.

Oto jak wygląda rekurencyjna funkcja silni:

int factorial(int n) {
    if (n <= 1) {           // Przypadek bazowy: 0! i 1! są równe 1
        return 1;
    }
    
    return n * factorial(n - 1);  // Krok rekurencyjny: n! = n × (n-1)!
}

Przypadek bazowy zatrzymuje rekurencję, gdy n osiągnie 1 lub 0, i zwraca 1. Krok rekurencyjny mnoży bieżącą liczbę przez silnię następnej, mniejszej liczby. Gdy wywołasz factorial(4), obliczy 4 × 3 × 2 × 1, wykonując kolejne wywołania aż do osiągnięcia przypadku bazowego, a następnie pomnoży wszystkie wyniki przez siebie, gdy wywołania będą zwracać wartości.

Wyzwanie

Łatwy

Utwórz program, który implementuje rekurencyjną funkcję silni i używa jej do obliczania silni dla różnych wartości wejściowych. To wyzwanie sprawdzi Twoje zrozumienie działania rekurencji: funkcja będzie wywoływać samą siebie ze zmodyfikowanymi parametrami, aż osiągnie przypadek bazowy.

Dane wejściowe:

Liczba całkowita n określająca liczbę, dla której należy obliczyć silnię

Twój program powinien:

Utworzyć rekurencyjną funkcję o nazwie factorial, która przyjmuje parametr typu całkowitego i zwraca liczbę całkowitą
Funkcja powinna implementować przypadek bazowy: jeśli n jest mniejsze lub równe 1, zwróć 1
Funkcja powinna implementować krok rekurencyjny: zwróć n pomnożone przez silnię z n-1
W funkcji głównej odczytać wartość wejściową
Wywołać funkcję silni z wartością wejściową
Wypisać wynik w określonym formacie

Użyj dokładnie następującego formatu wyjściowego:

Factorial of [n] is [result]

Pamiętaj, że funkcja silni musi za każdym razem wywoływać samą siebie z mniejszą wartością, zbliżając się przy każdym wywołaniu rekurencyjnym do przypadku bazowego. Przypadek bazowy zapobiega nieskończonej rekurencji, zatrzymując ją, gdy n osiągnie 1 lub 0. Krok rekurencyjny mnoży bieżącą liczbę przez silnię z kolejnej mniejszej liczby, budując końcowy wynik w miarę zwracania wartości przez kolejne wywołania funkcji.

Spróbuj swoich sił

#include <iostream>
using namespace std;

// TODO: Napisz tutaj funkcję obliczającą silnię

int main() {
    // Wczytaj dane wejściowe
    int n;
    cin >> n;
    
    // TODO: Wywołaj funkcję obliczającą silnię i zapisz wynik
    
    // Wyświetl wynik
    cout << "Factorial of " << n << " is " << result << endl;
    
    return 0;
}