Como posso implementar o algoritmo de Euclides usando recursividade?

Question

O algoritmo de Euclides para achar o máximo divisor comum de dois números x e y :
a) Se y é divisor de x, então y é o máximo divisor comum de x e y .
b) Em caso contrário, o maior divisor comum de x e y é igual ao máximo divisor comum de y e o resto de x dividido por y .

Answer 1

O algoritmo foi implementado usando a linguagem python. Dentro da função euclides, o condicional verifica a relação entre x e y. Se x é divisível por y, então x é o máximo divisor comum; caso contrario, chama, recursivamente, a função euclides para seguir procurando.

def euclides(x, y):
    if y!=0:
        return euclides(y, x%y)
    return x

if __name__ == '__main__':
    print euclides(594,216)
    print euclides(5,25)

Comments

A implementação está correta.
É importante destacar a condição de parada desse algoritmo. Quando o segundo argumento da função é zero, conclui-se que o argumento anterior (x da chamada anterior) era múltiplo, pois x%y = 0 => x é múltiplo de y. Então y é o máximo divisor comum (representado por x na última chamada da função).