Questão de Gestão de TI · FGV DPGE-RJ 2014 (nº 55)

Esta função recursiva calcula o Máximo Divisor Comum (MDC) de dois números inteiros usando o Algoritmo de Euclides. O MDC é o maior número que divide ambos os números sem deixar resto, e x MOD y é o resto da divisão de $x$ por $y$.

• (A) Incorreta: O valor 0 só seria retornado se o primeiro argumento (a) fosse 0 na chamada final, o que não acontece aqui.
• (B) Incorreta: 1 é um divisor comum, mas não o maior divisor comum de 30 e 21.
• (C) Correta: Vamos traçar a execução:
  • f(30, 21): b (21) não é 0. Chama f(21, 30 MOD 21).
  • 30 MOD 21 = 9. Então, chama f(21, 9).
  • f(21, 9): b (9) não é 0. Chama f(9, 21 MOD 9).
  • 21 MOD 9 = 3. Então, chama f(9, 3).
  • f(9, 3): b (3) não é 0. Chama f(3, 9 MOD 3).
  • 9 MOD 3 = 0. Então, chama f(3, 0).
  • f(3, 0): b (0) é 0. Retorna a (3).
    O valor final retornado é 3, que é o MDC de 30 e 21.
• (D) Incorreta: 7 não é um divisor de 30, nem de 21.
• (E) Incorreta: O valor 9 aparece como um resto intermediário (30 MOD 21 = 9) durante o cálculo. Um erro comum é confundir um resto intermediário com o resultado final do MDC, que só é encontrado quando o resto da divisão se torna 0.