UêbaRecursividade: Algoritmo recursivo para MDC
Continuando minha série de algoritmos clássicos, abordarei novamente o problema de MDC (Máximo Divisor Comum), mas desta vez com recursividade. Eu recomendo fortemente a leitura do meu artigo com uma solução para o algoritmo de MDC.
Recursão
Para tratarmos um problema utilizando recursão, devemos propor uma solução do problema como um problema menor, mas do mesmo tipo, e com alguma solução trivial. Nem todo problema pode ser resolvido com recursão. Também é verdade que alguns problemas tratados com recursão podem ser resolvidos sem ela, mas nem todos.
Solução recursiva para MDC
No caso do MDC, a solução recursiva está na solução como proposta em meu artigo anterior:
tomamos os dois números inteiros e dividimos o maior pelo menor. Se o resto da divisão for zero, temos que o menor daqueles números é o MDC entre eles. Se o resto não for zero, este procedimento deve ser repetido usando o menor número no lugar do maior e o resto no lugar do menor.
Podemos pensar da seguinte forma: calcula-se o resto da divisão do maior número pelo menor. Se o resto for igual a zero o MDC é o menor dos números. Se não for, o MDC será o mesmo que o MDC do menor com o resto. Neste caso teremos proposto uma solução que trata o problema como um subproblema, tendo uma solução trivial (quando o resto for zero).
Algoritmo
Vamos ao algoritmo:
<html>
<head>
<title>Algoritmos | MDC</title>
<meta http-equiv="Content-Type"
content="text/html; charset=UTF-8" />
<meta name="description"
content="Algoritmo de Euclides para solução de MDC"
/>
<meta name="author"
content="Cid Rodrigues de Andrade" />
<script>
function mdc(maior,menor) {
var resto = maior % menor;
if ( resto == 0 ) {
return menor;
} else {
return mdc(menor,resto);
}
}
window.onload=function(){
var num1 = prompt("Digite número #1","");
var num2 = prompt("Digite número #2","");
if (num1 > 0 && num2 > 0) {
if (num1 > num2) {
maior = num1;
menor = num2;
} else {
maior = num2;
menor = num1;
}
alert ("MDC entre " + num1 + " e " +
num2 + " é " + mdc(maior,menor));
} else {
alert ("Valores devem ser superiores a zero");
}
}
</script>
</head>
<body></body>
</html>