Come calcolare il fattoriale di un numero

È facile calcolare manualmente un fattoriale, ma come farlo in modo programmatico, nel modo più pulito possibile?

Il fattoriale di un numero è un importante concetto matematico. Puoi usarlo per eseguire permutazioni e combinazioni, scrivere espressioni esponenziali e logaritmiche e calcolare la probabilità.

Lo usi per trovare i diversi modi in cui puoi progettare una disposizione dei posti a sedere o scegliere le magliette per la tua vacanza alle Maldive. Ma come si calcola il fattoriale di un numero?

Qual è il fattoriale di un numero?

Il fattoriale di un numero positivo è il prodotto di tutti gli interi positivi minori o uguali al valore del numero stesso. Un numero seguito da un punto esclamativo(!) indica il fattoriale di un numero. Rappresenti il fattoriale di cinque come 5! e calcolarlo come:

5!=5 * 4 * 3 * 2 * 1=120

Un altro modo per visualizzarlo è:

5!=5*4! dove 4!=4 * 3!, 3!=3*2! e così via fino ad ottenerne 1!=1 * 0! che è 1.

Utilizzerai questo concetto per costruire il nostro programma fattoriale utilizzando un concetto popolare chiamato ricorsione.

Cos'è la ricorsione?

La ricorsione è un processo in cui una funzione richiama se stessa. Uno dei principali vantaggi di questo processo è che suddivide un problema più grande in parti più piccole. Ciò rende il problema più facile da risolvere.

È possibile utilizzare la ricorsione per risolvere i problemi appropriati in tre semplici passaggi:

Trova il caso base: se una funzione richiama sempre se stessa, il processo sarà infinito. Per evitare che ciò accada, definisci un caso base che diventi il punto di arresto logico per la tua funzione. Ad esempio, in un programma fattoriale, interrompere il calcolo a zero. Questo diventa il caso base del problema.
Trova la relazione tra il problema e i sottoproblemi: scomponi il problema più grande in un sottoproblema. Ad esempio, il problema è trovare il fattoriale di cinque. Supponiamo di avere la risposta del fattoriale di quattro, ovvero 24. Come otterrai il fattoriale di cinque utilizzando 24? Moltiplicando cinque stesso in esso. Questa è la relazione tra il problema e il sottoproblema.
Generalizza la relazione trovata nel passaggio 2: Ora che hai la relazione, generalizzala in termini di n. Quindi il fattoriale di un numero n è il prodotto di n per il fattoriale di n-1.

Puoi utilizzare questo concetto per trovare la somma di n numeri naturali, calcolare MCD, MCM, la serie di Fibonacci e controllare i numeri primi.

Pseudocodice per la funzione fattoriale utilizzando la ricorsione

Ecco come usi la ricorsione e scrivi lo pseudo codice per costruire il tuo programma in qualsiasi linguaggio. Con linguaggi diversi, la sintassi e l'esecuzione cambiano ma la logica rimane intatta.

function Fact(n)
    If n == 0 then // base case
        Return 1 
    Return n * Call Fact(n - 1) // generalized relation

Programma fattoriale in C

C è stato il primo linguaggio di programmazione di alto livello indipendente dalla piattaforma. Ha una sintassi rigorosa, distingue tra maiuscole e minuscole ed esegue il codice con la massima velocità. È un linguaggio di programmazione procedurale e quindi dichiari qualsiasi funzione sopra la funzione principale. Ecco come puoi costruire il programma fattoriale usando la ricorsione in linguaggio C:

Puoi trovare l'intero codice sorgente del programma fattoriale utilizzando la ricorsione in C, Java e Python in questo repository GitHub.

Importa il file di intestazione di output di input standard per visualizzare l'output sullo schermo.
```
#include <stdio.h>
```
Definisci la funzione fatto e prendi il numero intero n come argomento.
```
int fact(int n) {
```
Scrivi il caso base della funzione utilizzando l'istruzione if e controlla la sua uguaglianza utilizzando ==. Se n è uguale a zero, restituisce uno.
```
    if (n == 0)
        return 1;
```
Scrivi l'equazione generalizzata e restituisci il prodotto di n con una chiamata di funzione del sottoproblema n-1.
```
    return n * fact(n - 1);
}
```
Dichiara la funzione main e inizializza una variabile di tipo intero per memorizzare il numero di cui vuoi trovare il fattoriale.
```
int main() {
    int num = 5;
```
Visualizza il fattoriale del numero utilizzando la funzione printf(). %d è l'identificatore del formato decimale. Utilizza ciascuno degli identificatori di formato per sostituirlo con il numero di cui desideri trovare il fattoriale e ottieni il risultato chiamando la funzione.
```
    printf("Factorial of %d is %d", num, fact(num));
    return 0;
}
```

Programma fattoriale in Java

Java è un linguaggio di programmazione compilato ed è indipendente dalla piattaforma. Memorizzi tutto il codice all'interno di una classe e l'esecuzione inizia dalla funzione principale. Fa distinzione tra maiuscole e minuscole e ha una sintassi rigorosa. Il codice è un po' più lungo ma più veloce rispetto a Python. Ecco come puoi costruire il programma fattoriale usando la ricorsione in Java:

Definire la classe Main.
```
class Main {
```
Definire una funzione statica con tipo restituito int che accetta una variabile n di tipo intero. Hai dichiarato un metodo statico poiché anche il metodo principale in Java è dichiarato statico. Inoltre, non è possibile chiamare un metodo non statico da un'istanza statica.
```
    static int fact(int n) {
```
Scrivi il caso base della funzione utilizzando l'istruzione if e controlla la sua uguaglianza utilizzando ==. Se n è uguale a zero, restituisce uno.
```
        if (n == 0)
            return 1;
```
Scrivi l'equazione generalizzata e restituisci il prodotto di n con una chiamata di funzione del sottoproblema n-1.
```
        return n * fact(n - 1);
    }
```
Dichiarare la funzione main in Java. Dichiara il modificatore di accesso come pubblico, in modo che possa essere accessibile da tutte le altre classi e metodi. Dichiari la funzione main come statica in modo che il compilatore possa invocarla senza istanziare la classe. Il tipo restituito è void e accetta argomenti di tipo String. Memorizza il numero di cui vuoi trovare il fattoriale.
```
    public static void main(String[] args) {
        int num = 5;
```
Utilizza il metodo println(), un'istanza della classe PrintStream, definita nella classe System per visualizzare il fattoriale del numero.
```
        System.out.println("Factorial of " + num + " is " + fact(num));
    }
}
```

Programma fattoriale in Python

Scrivere codice in Python è semplicissimo e divertente. Poiché si tratta di un linguaggio interpretato indipendente dalla piattaforma, non è necessario dichiarare il tipo di dati delle variabili. Si evita inoltre di dover dichiarare classi e importare librerie per un programma così semplice. Il parco giochi è pronto per iniziare a programmare.

La sintassi è più semplice, con una lunghezza del codice ridotta ma richiede un po' più di tempo per l'esecuzione rispetto agli altri linguaggi. Ecco come puoi costruire il programma fattoriale usando la ricorsione in Python:

Definire la funzione fact che accetta come argomento n.
```
def fact(n):
```
Scrivi il caso base della funzione utilizzando l'istruzione if e controlla la sua uguaglianza utilizzando ==. Se n è uguale a zero, restituisce uno.
```
    if n == 0:
        return 1
```
Scrivi l'equazione generalizzata e restituisci il prodotto di n con una chiamata di funzione del sottoproblema n-1.
```
    return n * fact(n-1)
```
Memorizza il numero di cui vuoi trovare il fattoriale e visualizzalo utilizzando l'istruzione print.
```
num = 5;
print("Factorial of", num, "is", fact(num))
```

Esistono molte applicazioni della ricorsione

La ricorsione è un modo efficace per risolvere i problemi. È il punto cruciale dell'intelligenza artificiale e trova usi nel mondo reale nei giochi puzzle come gli scacchi o il Sudoku.

È anche un metodo potente per ordinare strutture di dati come Tree o algoritmi di ordinamento come Quick sort e Merge sort. Potresti anche utilizzare la ricorsione nella ricerca di algoritmi come la ricerca binaria, espressioni matematiche come la serie di Fibonacci e altro ancora.