Observe o algoritmo a seguir, expresso numa pseudolinguagem. function xpto(u, v) begin if v = 0 then return u else return xpto(v, u mod v); end; Dado que, numa expressão do tipo x mod y, o operador mod retorna o resto de divisão inteira de x por y, é correto afirmar que a expressão xpto(342, 162) retorna:
- A)0;
Errada, porque a função nao termina em 0 neste caso; 0 aparece apenas como resto intermediario antes do retorno final.
- B)1;
Errada, porque 1 nao surge em nenhuma das chamadas recursivas desse par de valores.
- C)9;
Errada, porque 9 nao eh o resto nem o valor devolvido pelo caso base da recursao.
- D)18;
Certa, porque a sequencia recursiva leva a xpto(18, 0), e o caso base faz a função retornar 18.
- E)80.
Errada, porque 80 nao tem relacao com as divisões sucessivas entre 342 e 162.
Gabarito: D
A função apresentada é uma versão clássica do algoritmo de Euclides, usada para encontrar o máximo divisor comum (MDC) entre dois números. A lógica é simples e elegante: se o resto da divisão do segundo número por zero? Não, aqui o teste é se v = 0, a função devolve u; caso contrário, ela chama a si mesma trocando os valores e usando o resto da divisão. Isso vai reduzindo os números até chegar ao caso base. No exemplo, voce calcula assim: xpto(342, 162). Como 162 nao eh zero, faz-se 342 mod 162, que da 18, e a chamada vira xpto(162, 18). Agora 18 nao eh zero, entao calcula-se 162 mod 18, que da 0, ficando xpto(18, 0). Aí entra o caso base e a função retorna 18. Ou seja, o algoritmo está encontrando o MDC de 342 e 162, e o resultado é 18. A ideia central da questão é perceber a recursao e acompanhar as chamadas sem se perder no caminho. Quem reconhece o algoritmo de Euclides mata a questão sem sofrimento.