Algorithme d'Euclide étendu, version récursive

On ajoute une variable globale niveau et des fonctions d'affichage des résultats intermédiaires (qu'on ne détaille pas).

int niveau = 0;
void afficher1 (...);
void afficher2 (...);
void afficher3 (...);
void afficher4 (...);

long pgcd (long a, long b, long *u, long *v) {
  long q, r, d, s, t;
  
  niveau++;
  afficher1 (niveau, a, b, u, v, &s, &t);
  
  q = a / b;
  r = a % b;
  if (r == 0) {
    *u = 0;
    *v = 1;
    afficher2 (niveau, *u, *v);
    niveau--;
    return b;
  }
  d = pgcd (b, r, &s, &t);
  afficher3 (niveau, d, s, t);
  *u = t;
  *v = s - q * t;
  afficher4 (*u, *v);
  niveau--;
  return d;
}

void main (void) {
  long a, b, d, x, y;
  
  printf ("Entrer deux entiers : ");
  scanf ("%ld %ld", &a, &b);
  d = pgcd (a, b, &x, &y);
}
Voici une trace d'exécution :
Entrer deux entiers : 96 81

Niveauabd u*u v*v &ss &tt
1 96 81   effffc90   effffc8c   effffc08   effffc04  
2 81 15   effffc08   effffc04   effffb78   effffb74  
3 15 6   effffb78   effffb74   effffae8   effffae4  
4 6 3   effffae8   effffae4   effffa58   effffa54  
4         0   1        
3     3           0   1
        1   -2        
2     3           1   -2
        -2   11        
1     3           -2   11
        11   -13