Factorielle

Soit $n$ un nombre entier positif ou nul, le nombre $n!$, dit ''factorielle $n$'', est défini comme suit :

$$n! = 1\times 2 \times \ldots \times n = \prod_{i = 1}^n i$$

avec le cas particulier $0! = 1$. On observe que

$$n! = [1 \times \ldots \times (n-1)] \times n = [(n-1)!]\times n$$

Cette relation nous permet de réduire le calcul de la factorielle d'un nombre $n$ au calcul de la factorielle de $n-1$. En utilisant cette relation on obtient un algorithme récursif calculant la factorielle d'un nombre $n$.

• Observez bien que la condition d'arrêt est testée dès le début de l'exécution de l'algorithme, et qu'elle permet de calculer la valeur $0!$
• Dans le cas général, le calcul $n!$ se fait en passant par le calcul de $(n-1)!$. Comme la valeur passée en paramètre dans l'appel récursif est $n-1$ et est strictement inférieure à $n$, alors la séquence des valeurs passées en paramètre au fil des appels récursifs
  
  $$n \longrightarrow n - 1 \longrightarrow \ldots \longrightarrow 1 \longrightarrow 0$$
  
  
  est strictement décroissante et converge vers $0$. Il est très important de vérifier que quelques soient les valeurs passées en paramètre, la séquence de valeurs formée par les appels récursifs converge vers une valeur satisfaisant la condition d'arrêt, $0$ dans le cas présent.
• On remarque par ailleurs que cet algorithme n'est pas récursif terminal, en effet l'appel récursif précède une multiplication par $n$, la dernière instruction n'est donc pas un appel récursif.

Les doutes des plus sceptiques seront, je l'espère apaisés par la vue du sous-programme suivant :