Fattoriale

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

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

La funzione fattoriale è presente in molti linguaggi / applicazioni

  • Calc/Excel: FATTORIALE(x)
  • Octave: factorial(x)
  • Python: math.factorial(x)

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

Conclusioni

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)