Fattoriale – ValCon.It

Definizione

Formulazione

Esempio

Ricorsiva

$n!=\left\{ \begin{array}{ll}1&n=0,1\\ n(n-1)! & \text{altrimenti}\end{array} \right$

oppure

$f(n)=\left\{ \begin{array}{ll}1&n=0,1\\ n\cdot f(n-1) & \text{altrimenti}\end{array} \right$

5!=5*4!

4!=4*3!

3!=3*2!

2!=2*1!

1!=1

2!=2*1=2

3!=3*2=6

4!=4*6=24

5!=5*24=120

Iterativa

$n!=\left\{ \begin{array}{ll}1&n=0,1\\ n(n-1)\,\dots\,1 & \text{altrimenti}\end{array} \right$

1	5!=54321=120

La funzione fattoriale è presente in molti linguaggi / applicazioni

Quando non è presente è necessario codificarla.

Approssimazione

Per n molto grande si può rinunciare al valore esatto e utilizzare la formula di Stirling

$\displaystyle n! \approx \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$

Metodo	Pro	Contro
Ricorsivo	Formulazione molto semplice	n chiamate ~n moltiplicazioni
Iterativo	Semplice ripetizione Operazioni elementari	~n moltiplicazioni
Con formula	Numero di operazioni costante	Difficile da ricordare Numeri irrazionali Valore approssimato

Quindi

per il calcolo del fattoriale di n esistono più algoritmi
al crescere di n utilizzeremo l’algoritmo più conveniente (ricorsivo ⇒ iterativo ⇒ formula)