НОД через рекурсию в Java — алгоритм Евклида с примером

Программа принимает два положительных целых числа и вычисляет их наибольший общий делитель (НОД, G.C.D / H.C.F) с помощью рекурсии.

Пример: НОД двух чисел через рекурсию

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;
    }
}

Вывод:

G.C.D of 366 and 60 is 6.

В программе выше рекурсивная функция вызывается, пока n2 не станет равным 0. В конце n1 содержит НОД двух чисел.

Примечание

Шаги выполнения:

№	Рекурс. вызов	n1	n2	n1 % n2
1	hcf(366, 60)	366	60	6
2	hcf(60, 6)	60	6	0
Итог	hcf(6, 0)	6	0