Voici une autre façon d'implémenter la fonction pgcd en Haskell en utilisant une fonction récursive qui calcule toutes les diviseurs communs de a et b :
pgcd :: Int -> Int -> Int
pgcd a b = maximum $ diviseursCommuns a b
where
diviseursCommuns x y
| x == 0 || y == 0 = [ ]
| x == y = [x]
| x > y = diviseursCommuns (x - y) y
| otherwise = diviseursCommuns x (y - x)
Explications :
La fonction pgcd prend en entrée deux entiers positifs (a et b) et retourne leur PGCD.
Dans cette implémentation, on utilise une fonction récursive diviseursCommuns qui calcule tous les diviseurs communs de a et b.
La fonction récursive utilise une série de tests pour traiter les différents cas :
Si x ou y est nul, il n'y a pas de diviseurs communs et la fonction retourne une liste vide.
Si x et y sont égaux, ils sont eux-mêmes des diviseurs communs et la fonction retourne une liste contenant uniquement x.
Si x est supérieur à y, on soustrait y de x et on répète l'appel récursif avec les nouveaux arguments x - y et y.
Si x est inférieur à y, on soustrait x de y et on répète l'appel récursif avec les nouveaux arguments x et y - x.
La valeur renvoyée par la fonction diviseursCommuns est une liste contenant tous les diviseurs communs de a et b. Le PGCD est le plus grand diviseur commun de cette liste, obtenu en appliquant la fonction maximum.
Cette implémentation est également efficace et gère les mêmes cas que les précédentes implémentations. Elle peut sembler plus facile à comprendre pour certains débutants car elle utilise une fonction récursive explicite pour calculer tous les diviseurs communs.
.
