Bem-vindo à segunda parte da coleção de Algoritmos de Ciência da Computação. Neste desafio, continuaremos trabalhando na escrita de funções recursivas por meio do Algoritmo de Euclides. O "Algoritmo de Euclides" é um método para encontrar o máximo divisor comum (MDC) de dois números. Ele foi descrito originalmente pelo matemático grego Euclides.
Algoritmo
Para simplificar, vou me referir ao primeiro número como "a", ao segundo como "b" e ao resto como "r". O algoritmo pode ser dividido em quatro etapas:
- Certifique-se de que "a" >= "b". Se "a" < "b", troque-os.
- Encontre o resto. Divida "a" por "b" e defina "r" como o resto.
- "r" é zero? Nesse caso, encerre a função e retorne "b" (o segundo número).
- Defina "a" = "b" e "b" = "r" e recomece o algoritmo.
Instruções
Crie uma função recursiva que retorne o MDC entre dois números positivos usando o Algoritmo de Euclides.
Exemplos
euclidean(8, 6) ➞ 2
euclidean(25, 5) ➞ 5
euclidean(49, 14) ➞ 7
Observações
- Lembre-se de que, para encontrar o resto de dois números, você deve usar o operador módulo
%. - Os dois números serão positivos e nenhum deles será null.
- Vários dos desafios que serão abordados nesta coleção sobre algoritmos podem ser resolvidos sem recursão e sem implementar os algoritmos descritos em cada desafio. Peço encarecidamente a qualquer pessoa que resolva estes desafios que os faça conforme o planejado. Não entender os conceitos ensinados será um obstáculo para desafios posteriores e não ajudará ninguém a desenvolver suas habilidades como programador.
- Se você estiver travado, consulte a aba Resources, a aba Comments ou, se estiver realmente travado, use a aba Solutions para desbloquear as respostas.