EXERCICE. Montrer que n N, I'appel Fact(n) de la fonction Fact définie ci-dessous, se termine et calcule n!

FONCTION Fact(n : entier) : entier

DÉBUT

SI n = 0 ALORS

RETOURNE(1)

SINON

RETOURNE(n*Fact(n-l))

FINSI

FIN

CORRECTION

Prouvons la terminaison

A chaque appel n le paramètre décroit, puisque N est un ensemble ordonné bien fondé, il n'existe pas de suite infini décroissante, donc n s'annulera.

Quand n s'annule on retourne 1. Cela termine les appels récurssifs, on dépile alors l'ensemble des appels précédents. Donc le programme se termine.

---

Montrons que n N, I'appel Fact(n) calcule n!

On considère la propriété P: "Fact(n)=n!"

Il y a un seul cas où la fonction retourne directement une valeur. Si n=0 alors le résultat est 1. Pour n=0 la propriété P est vérifiée.

Supposons P(n) vrai.

Fact(n+1)=(n+1)*Fact(n)

et

Fact(n)=n!

Donc Fact(n+1)=(n+1)*(n!) est P(n+1) est vérifié.