Нахождение наибольшего общего делителя (НОД) при помощи рекурсии

Описание задачи

Программа принимает на вход два числа и находит наибольший общий делитель (НОД) с использованием рекурсии.

Решение задачи

1. Принимаются два числа, которые сохраняются в отдельные переменные.
2. Передаем оба числа в рекурсивную функцию в качестве аргумента.
3. В качестве базового условия рекурсии принимаем равенство нулю второго числа (второго аргумента функции). В этом случае результатом работы функции является первое число (первый аргумент функции).
4. В противном случае снова рекурсивно вызываем эту функцию и в качестве первого аргумента передаем ей второй аргумент из предыдущего вызова функции, а в качестве второго — остаток от деления первого аргумента на второй аргумент.
5. Когда функция завершит свою работу, ее результатам будет первый аргумент из последнего вызова этой функции. Он и будет наибольшим общим делителем (НОД).
6. Выводим результат на экран.
7. Конец.

Исходный код

Ниже дан исходный код, который осуществляет нахождение наибольшего общего делителя (НОД) с использованием рекурсии. Результаты работы программы также даны ниже.

def gcd(a, b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)
a = int(input("Введите первое число:"))
b = int(input("Введите второе число:"))
GCD = gcd(a, b)
print("НОД: ")
print(GCD)

Объяснение работы программы

1. Пользователь вводит два числа и они записываются в переменные a и b.
2. Затем эти два числа передаются в качестве аргументов в рекурсивную функцию gcd().
3. В качестве базового условия рекурсии принимаем равенство 0 второго аргумента функции: b == 0. В этом случае результатом работы функции будет первый аргумент a.
4. В противном случае снова рекурсивно вызываем нашу функцию следующим образом: gcd(b, a % b). То есть, в качестве первого аргумента передаем ей второй аргумент из предыдущего вызова функции (b), а в качестве второго —остаток от деления a на b.
5. Когда функция завершит свою работу, ее результатам будет первый аргумент из последнего вызова этой функции. Он и будет наибольшим общим делителем (НОД).
6. Выводим результат работы функции на экран.

Результаты работы программы

Пример 1:
Введите первое число:5
Введите второе число:15
НОД: 
5
 
Пример 2:
Введите первое число:30
Введите второе число:12
НОД: 
6