Exercice : PGCD

Le PGCD de deux entiers \(a\) et \(b\) peut être calculé à l’aide de la formule suivante :

\[\begin{split} \operatorname{pgcd}(a,b)= \begin{cases} a & \text{si $b = 0$} \\ \operatorname{pgcd}(b, a \bmod b) & \text{sinon}\,. \end{cases} \end{split}\]

1. Écrivez et testez la fonction récursive pgcd.

   BEGIN SOLUTION

   int pgcd(int a, int b) {
       if (b == 0) return a;
       return pgcd(b, a % b);
   }
   

   END SOLUTION

2. Comparez votre implémentation avec l’implémentation itérative donnée dans l’exercice 4 du TD 2.

   BEGIN SOLUTION

   La version récursive est une traduction bien plus directe et lisible de la formule mathématique. Toutefois, suivant le compilateur, les performances peuvent être nettement moins bonnes.

   END SOLUTION