Recur9. Описать рекурсивную функцию NOD(A, B) целого типа, находящую наибольший общий делитель (НОД) двух целых положительных чисел A и B, используя алгоритм Евклида:
НОД(A, B) = НОД(B, A mod B), если \(B \neq 0\); НОД(A, 0) = A.
С помощью этой функции найти НОД(A, B), НОД(A, C), НОД(A, D), если даны числа A, B, C, D.

Решение на Python 3:

def NOD(A,B):
if B != 0:
return NOD(B,A%B)
else:
return A

A = 81
B = 27
C = 6
D = 20

print("A = ",A)
print("B = ",B)
print("C = ",C)
print("D = ",D)

print("NOD({0},{1}) = {2}".format(A,B,NOD(A,B)))
print("NOD({0},{1}) = {2}".format(A,C,NOD(A,C)))
print("NOD({0},{1}) = {2}".format(A,D,NOD(A,D)))