El algoritmo de Euclides nos permite hallar el máximo común divisor entre dos números y su definición es, por naturaleza, recursiva. Veamos un ejemplo en pseudocódigo.
Recordemos que la operación mod (o “módulo”) retorna el resto de la división. Por ejemplo: 5 mod 2 retornará 1, ya que es el resto de dividir 5 / 2.
Click aquí para una versión accesible de la infografía (apta para lectores electrónicos)
Algoritmo de Euclides: máximo común divisor (recursivo)
La fórmula de máximo común divisor (“mcd”) se define como:
x si y=0;
mcd(y, resto(x,y)) si y>0.
Algoritmo en pseudocódigo:
Función mcd(x: entero, y: entero)
si y == 0:
retornar x
si no:
retornar mcd(y, (x mod y))
fin mcd
Entrada: dos números enteros: x, y. Donde x>0, y>=0.
Salida: el máximo común divisor de ambos.