Plusieurs façons de calculer une factorielle en Python

Calculer une factorielle en Python n’est pas très compliqué quand on sait ce qu’est une factorielle…

calcul factorielle en Python

Définition d’une factorielle

Du point de vue mathématiques, la factorielle d’un entier naturel n est le produit noté n! tel que :$$n!=1\times2\times3\times4\times\cdots\times(n-1)\times n.$$Par exemple,

  • \(5!=1\times2\times3\times4\times5\)
  • \(2!=1\times2\)
  • \(1!=1\)
  • \(0!=1\) (par convention)

Une première proposition de script pour calculer une factorielle en Python

À partir de cette définition, on peut concevoir un programme Python comme celui-ci:

def factorielle(n):
    if n == 0:
        return 1
    else:
        F = 1
        for k in range(2,n+1):
            F = F * k
        return F

Ainsi, en console, on a par exemple:

>>> factorielle(5)
120

Que s’est-il passé ici pour voir ce résultat ?

On appelle factorielle(5) : quand on entre dans la fonction factorielle, on teste avant tout si l’argument vaut 0, ce qui n’est pas le cas donc on passe à la ligne 5. On initialise alors une variable F à 1, puis on entre dans une boucle où la variable k varie de 1 à n. À chaque passage, la valeur contenue dans F est multipliée par k, ce qui donne (sous forme de tableau):

k2345
F11×2 = 22×3 = 66×4 = 2424×5 = 120

Le résultat finale retourné est donc 120.

Une autre approche de la factorielle en Python

On peut remarquer que si on pose :$$f(n)=n!$$ alors,$$\begin{align}f(n+1)&=(n+1)!\\&=\underbrace{1\times2\times3\times\cdots\times n}_{=n!}\times(n+1)\\&=f(n) \times (n+1)\end{align}$$

On peut alors imaginer un deuxième programme légèrement différent du premier:

def factorielle(n):
    if n == 0:
        return 1
    else:
        return n  * factorielle(n-1)

C’est ce que l’on appelle la forme récursive du programme. On l’appelle ainsi car pour calculer la factorielle d’un entier n, on fait appel à la factorielle de l’entier précédent, à l’instar d’une suite récursive de la forme \(u_{n+1}=f(u_n)\).

La liste des premières factorielles en Python

Maintenant que l’on sait calculer une factorielle, on pourrait créer une liste des premières valeurs, mais de façon intelligente tant qu’affaire. Ainsi, on ne va pas écrire:

F = []
for k in range(50):
    F += [ factorielle(k) ]

Ben non… Et je suis sûr que vous voyez pourquoi… Ben oui ! C’est tout de même ballot de faire toutes ces opérations à chaque fois que l’on veut calculer un terme de la liste. Par exemple, pour le n-ième élément de la liste, on demande de calculer factorielle(n – 1), soit n – 2 opérations alors qu’il suffirait de multiplier l’élément précédent par (n – 1).

Autrement dit, ce programme nécessite:$$0+1+2+3+\cdots+(n+1)=\frac{n(n-1)}{2}$$multiplications (pour les connaisseurs, je ne parle pas de la complexité du programme, mais cette complexité est du même ordre de grandeur), soit un ordre de grandeur de n²/2 multiplications.

Il est donc préférable d’utiliser ce programme:

F = [1]
for k in range(1,50):
    F += [ F[k-1] * k ]

Ce programme est bien plus rapide pour les grandes valeurs de n car il ne nécessite que n produits (qui est bien moins grand que n²/2).

Et n’oubliez pas que si vous avez des problèmes en maths, je peux vous aider par webcam !