Nous allons voir sur cette page plusieurs manières de calculer une factorielle en Python.

python factorielle

Qu'est-ce qu'une factorielle du point de vue mathématique ?

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)

Python et factorielle: une approche naïve

À partir de la définition mathématique précédente, on peut imaginer une première approche d’un programme Python nous permettant de calculer une factorielle :

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

      return F
>>> factorielle(5) 
120

Exécution pas à pas du programme

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):
k 2 3 4 5
F 1 1×2 = 2 2×3 = 6 6×4 = 24 24×5 = 120

Le résultat final retourné est donc 120.

Python et factorielle: une approche récursive

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)\).

Une variante avec la fonction lambda.

On peut légèrement simplifier la syntaxe précédente tout en gardant la forme récursive à l’aide de la fonction lambda de Python:

 

factorielle = lambda n: n * factorielle(n-1) if n != 0 else 1

Vous me croyez si vous voulez, mais je vous assure que cette simple ligne fait le même job que le programme précédent ! En mode console, on a:

 

>>> factorielle(7)
5040

Python et factorielle: en utilisant une liste

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.append( 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 multiplications, plus une multiplication par n, 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=\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 \(\frac{n^2}{2}\) multiplications.

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

F = [1]
for k in range(1,50):
    F.append( 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 \(\frac{n^2}{2}\)).

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

Cet article a 2 commentaires

  1. Donat jean

    super !! je bricole avec Python depuis plus d’un an ,mais jamais eu l’occasion d’utiliser les factorielles .j’essaie d’écrire un programme de statistique
    sur les courses de chevaux . je suis à la retraite et je m’éclate avec les classes,les méthodes mon livre de chevet : apprendre à programmer avec Python 3
    de Gerard Swinnen .tres bon bouquin mais pas question de factorielle !!
    par hasard je tombe sur un pb de factorielle
    merçi encore

    1. Les factorielles sont utilisées dans certains modules utiles. À chaque fois qu’il il a une opération de permutation de combinaison, etc., il y a de la factorielle. Il ne faut pas oublier que la performances d’un programme dépend des outils mathématiques utilisés pour le concevoir

Laisser un commentaire