Questão de Redes de Computadores · FGV DPGE-RJ 2014 (nº 53)

Recursão é quando uma função chama a si mesma para resolver um problema, dividindo-o em partes menores até chegar a um caso base. A função f(a, b) implementa o Algoritmo de Euclides para encontrar o Máximo Divisor Comum (MDC) entre a e b.

• f(30, 21): b (21) não é 0. Chama f(21, 30 MOD 21).
  • 30 MOD 21 = 9.
• f(21, 9): b (9) não é 0. Chama f(9, 21 MOD 9).
  • 21 MOD 9 = 3.
• f(9, 3): b (3) não é 0. Chama f(3, 9 MOD 3).
  • 9 MOD 3 = 0.
• f(3, 0): b (0) é 0. Retorna a, que é 3.

(A) Incorreta: O Máximo Divisor Comum (MDC) de números positivos nunca é zero.
(B) Incorreta: O MDC de 30 e 21 não é 1, pois eles possuem divisores comuns maiores que 1 (como o próprio 3).
(C) Correta: A execução da função segue os passos do Algoritmo de Euclides: f(30, 21) -> f(21, 9) -> f(9, 3) -> f(3, 0). No caso base b = 0, a função retorna a, que é 3.
(D) Incorreta: O valor 7 é um divisor de 21, mas não de 30, portanto não pode ser o MDC.
(E) Incorreta: Este é o resto da primeira divisão (30 MOD 21 = 9). A armadilha da banca é fazer o aluno parar a execução prematuramente, retornando um valor intermediário em vez de continuar a recursão até o caso base b = 0.