Neste programa, você aprenderá a encontrar o GCD (Greatest Common Divisor) ou HCF usando uma função recursiva em Java.
Para entender este exemplo, você deve ter conhecimento dos seguintes tópicos de programação Java:
- Métodos Java
- Java Recursion
Este programa pega dois inteiros positivos e calcula GCD usando recursão.
Visite esta página para saber como calcular o GCD usando loops.
Exemplo: GCD de dois números usando recursão
public class GCD ( public static void main(String() args) ( int n1 = 366, n2 = 60; int hcf = hcf(n1, n2); System.out.printf("G.C.D of %d and %d is %d.", n1, n2, hcf); ) public static int hcf(int n1, int n2) ( if (n2 != 0) return hcf(n2, n1 % n2); else return n1; ) )
Resultado
GCD de 366 e 60 é 6.
No programa acima, a função recursiva é chamada até que n2 seja 0. No final, o valor de n1 é o GCD ou HCF dos dois números dados.
Etapas de execução| Não. | Chamada recursiva | n1 | n2 | n1% n2 |
|---|---|---|---|---|
| 1 | hcf (366, 60) | 366 | 60 | 6 |
| 2 | hcf (60, 6) | 60 | 6 | 0 |
| Final | hcf (6, 0) | 6 | 0 | - |
