PGCD récursif — exercice corrigé de programmation Java (école d'ingénieur) (chapitre 4)

PGCD récursif

Méthodes · niveau 2

Énoncé

L'algorithme d'Euclide repose sur deux propriétés : $pgcd (a, 0) = a$ , et, pour $b > 0$ , $pgcd (a, b) = pgcd (b, a mod b)$ .

Écrire la méthode récursive static int pgcd(int a, int b), avec son commentaire de documentation (précondition, postcondition).
Donner la suite des appels effectués par pgcd(84, 36) et le résultat.
Pourquoi la récursivité se termine-t-elle toujours ?

Corrigé


/**
 * Retourne le plus grand diviseur commun de a et b.
 * Précondition : a >= 0, b >= 0, a et b non tous deux nuls.
 * Postcondition : le résultat divise a et b, et tout diviseur commun le divise.
 */
static int pgcd(int a, int b) {
    if (b == 0) return a;                    // cas de base
    return pgcd(b, a % b);                   // a % b < b : le second argument diminue
}

En ajoutant un affichage en tête de la méthode, on obtient la suite des appels :


  pgcd(84, 36)
  pgcd(36, 12)
  pgcd(12, 0)
pgcd(84, 36) = 12

Terminaison : à chaque appel, le second argument est remplacé par a % b, qui est un entier positif ou nul strictement inférieur à $b$ . Une suite d'entiers positifs strictement décroissante est finie : on atteint forcément $b = 0$ , le cas de base.