Fattoriale ricorsivo

Fa parte della sezione Logica e flusso del percorso C++ di Coddy. Lezione 46 di 56.

Il fattoriale di un numero è un esempio perfetto per mostrare la ricorsione in azione. Il fattoriale di n (scritto come n!) è il prodotto di tutti gli interi positivi da 1 a n. Per esempio, 5! = 5 × 4 × 3 × 2 × 1 = 120.

Ciò che rende il fattoriale ideale per la ricorsione è che può essere definito in termini di sé stesso: n! = n × (n-1)!. Ciò significa che, per calcolare 5!, moltiplichi 5 per 4! e, per calcolare 4!, moltiplichi 4 per 3!, e così via.

Ecco come appare una funzione fattoriale ricorsiva:

int factorial(int n) {
    if (n <= 1) {           // Caso base: 0! e 1! sono entrambi uguali a 1
        return 1;
    }
    
    return n * factorial(n - 1);  // Passo ricorsivo: n! = n × (n-1)!
}

Il caso base interrompe la ricorsione quando n raggiunge 1 o 0, restituendo 1. Il passaggio ricorsivo moltiplica il numero corrente per il fattoriale del numero successivo più piccolo. Quando chiami factorial(4), calcola 4 × 3 × 2 × 1 effettuando chiamate successive fino a raggiungere il caso base, quindi moltiplica tutti i risultati man mano che le chiamate ritornano.

Sfida

Facile

Crea un programma che implementi una funzione ricorsiva per il fattoriale e la usi per calcolare i fattoriali di diversi valori di input. Questa sfida metterà alla prova la tua comprensione del funzionamento della ricorsione, facendo sì che una funzione chiami sé stessa con parametri modificati finché non raggiunge un caso base.

Verrà fornito il seguente input:

Un intero n che rappresenta il numero di cui calcolare il fattoriale

Il tuo programma dovrebbe:

Creare una funzione ricorsiva chiamata factorial che accetta un parametro intero e restituisce un intero
La funzione dovrebbe implementare il caso base: se n è minore o uguale a 1, restituisci 1
La funzione dovrebbe implementare il passaggio ricorsivo: restituisci n moltiplicato per il fattoriale di n-1
Nella funzione main, leggi il valore di input
Chiama la funzione factorial con il valore di input
Stampa il risultato usando il formato specificato

Usa il seguente formato di output esatto:

Factorial of [n] is [result]

Ricorda che la funzione factorial deve chiamare sé stessa ogni volta con un valore più piccolo, avvicinandosi al caso base a ogni chiamata ricorsiva. Il caso base evita la ricorsione infinita interrompendola quando n raggiunge 1 o 0. Il passaggio ricorsivo moltiplica il numero corrente per il fattoriale del numero successivo più piccolo, componendo il risultato finale man mano che le chiamate della funzione restituiscono i propri valori.

Provalo tu

#include <iostream>
using namespace std;

// TODO: Scrivi qui la tua funzione per calcolare il fattoriale

int main() {
    // Leggi l'input
    int n;
    cin >> n;
    
    // TODO: Chiama la funzione per calcolare il fattoriale e memorizza il risultato
    
    // Visualizza il risultato
    cout << "Factorial of " << n << " is " << result << endl;
    
    return 0;
}