**TD5 - Récurrence**

1. factorielle(n) {
if(n == 0);
return 1;
else
return n*factorielle(n-1);
}
2. puissance(k,n) {
if(n == 0) {
return 1;
} return k*puissance(k,n-1);
}
3. exponentiation(k,n) {
if(n == 0) return 1;
return puissance(k,exponentiation(k,n-1);

}

EX 2.

EXERCICE 3 :

1. pour tout a et b positif tel que a > b,
si b > 0 (le cas du sinon),
la fonction va être appelée avec euclide(b, a mod b)
b>= 0 --> vrai par hypothèse,
- a mod b >= 0 --> car a > b et par définition du modulo on a a mod b > 0 donc a mod b >= 0
- b > a mod b --> trivial,