Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como posso implementar o algoritmo de Euclides usando recursividade?

+1 voto
209 visitas
perguntada Set 5, 2016 em Programação Computacional por santiago (131 pontos)  
editado Set 6, 2016 por santiago

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 .

Compartilhe

1 Resposta

+1 voto
respondida Set 5, 2016 por santiago (131 pontos)  
editado Set 6, 2016 por santiago

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)
comentou Set 23, 2016 por Caue (231 pontos)  
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).
...