PGCD récursif

ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Calcul récursif d'un PGCD
» Méthodes non récursives , Autres exemples de récursion , Fonctions récursives (généralités)

Une fonction ou une procédure (sous-programme informatique) est dite récursive si elle fait appel à elle-même dans l'algorithme qui la définit. Actuellement, la majorité des langages de programmation accepte cette forme de programmation (récursion) extrêmement puissante et élégante, aboutissant à des programmes très concis et très proches de la formulation mathématique de l'algorithme étudié.

! Cependant, il ne s'agit pas d'en abuser car cette technique est généralement gourmande en kilo-octets de mémoire : chaque appel récursif oblige l'ordinateur à différer ses calculs en cours en empilant des variables auxiliaires (dites locales). La pile peut être rapidement saturée suivant la profondeur de la récursion.

➔ Il est d'ailleurs prouvé que tout algorithme récursif peut être remplacé par un algorithme itératif (de type récurrent : usage de boucles conditionnelles ou non).

Afin d'illustrer ce concept, et afin de contourner l'inévitable factorielle n , prenons le non moins incontournable exemple du calcul du PGCD selon l'algorithme d'Euclide.

Programmation de la méthode en JavaScript

La fonction go() est la fonction d'appel du programme. Par défaut, a = 504 et b = 396. Le pgcd est alors 36. On appréciera la simplicité récursive de la fonction pgcd ! L'instruction a%b retourne le reste de la division de a par b.

» fonctions mathématiques usuelles

<SCRIPT LANGUAGE=JavaScript>
function go()
{
a=504;b=396;
a=eval(prompt("a = ",a))
b=eval(prompt("b = ",b))
d=pgcd(a,b)
alert("pgcd("+a+","+b+") = "+d)
}
function pgcd(a,b)
{
if (b==0) {return a} else {return pgcd(b,a%b)}
}
</SCRIPT>

Analyse d'exécution du programme :

Appel n°1 : PGCD(504,396) : création des variables a = 504 et b = 396 , locales à la procédure.
L'ordinateur calcule le reste r₁ = a - bq où q est la partie entière de a/b : r₁ = 108 ≠ 0 joue le rôle de b pour l'appel n°2.
Appel n°2 : PGCD(396,r₁) = PGCD(396,108) : création du reste r₂ = 72 ≠ 0
Appel n°3 : PGCD(108,r₂) = PGCD(108,72) : création du reste r₃ = 36 ≠ 0
Appel n°4 : PGCD(72,r₃) = PGCD(72,36) : création du reste r₄ = 0
Appel n°5 : PGCD(36,0) : la fonction pgcd retourne a = 36 car b = 0 est nul.
En sortant de la fonction, l'ordinateur efface de la mémoire les variables auxiliaires r₁ à r₄, ce qui libère de la mémoire pour des calculs ultérieurs.

Quelques autres algorithmes récursifs dans ChronoMath :

Factorielle n (tableur) Un calcul de π Formule de Wallis (sur tableur) Fonction d'Ackermann

Nombres de Lucas Tri d'une liste Inversion d'une chaîne de caractères Suite de Fibonacci

➔ Pour en savoir plus :

Techniques récursives en programmation par D.W. Baron - Ed. Dunod, Paris - 1970
Les bases de la programmation par Jacques Arsac - Ed. Dunod informatique, Paris - 1983
Les algorithmes par Patrice Hernert - Que sais-je n° 2928, Ed. P.U.F., Paris - 1995