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 :

Quelques autres algorithmes récursifs dans ChronoMath :

 Pour en savoir plus :


© Serge Mehl - www.chronomath.com