Может кто-нибудь объяснить мне, как работает этот код? Я пытаюсь понять, как рекурсивные работы и как их писать. Новый студент, спасибо.Может ли кто-нибудь объяснить, как работает этот код? GCD, Recursive, Euclidian algorighm
def gcdRecur(a, b):
'''
a, b: positive integers
returns: a positive integer, the greatest common divisor of a & b.
'''
if b == 0:
return a
else:
return gcdRecur(b,a % b)
obj = gcdRecur(9,12)
print (obj)
Это должно быть дубликат, но это реализация алгоритма Евклида. Основной принцип заключается в том, что наибольший общий коэффициент a и b (где b < a, который он будет после максимального шага) также является наибольшим общим фактором b, а остальная часть, когда вы делите a на b. Повторяя этот шаг, вы переходите к случаю, когда в конечном итоге остаток равен 0 (потому что можно показать, что остаток продолжает уменьшаться), а затем gcf - это другой номер. Таким образом, в вашем примере из 9 и 12 он переходит к 12 и 9, затем 9 и 3, затем 3 и 0 и возвращает 3, что является правильным. Способ работы функции - это рекурсия, а это означает, что она вызывает себя.
Это реализация Euclid's algorithm.
Вкратце, % является оператором модуля, который возвращает остаток от деления первого операнда на второй, так a % b делит 9 на 12, который является 0 с остатком 9. рекурсии чередуется аргументы, так что следующая операция будет 12 % 9 == 3, а затем 9 % 3 == 0, потому что 3 делит 9 без остатка. 3 также делит 12, потому что это сумма самого себя и 9, число, которое оно делит без остатка.
Добро пожаловать в stackoverflow :) Вместо того, чтобы спрашивать «может ли кто-нибудь объяснить мне, как это работает», было бы лучше, если бы вы прочитали страницу википедии по Евклидову алгоритму и задали более конкретный вопрос о том, «застрял». В противном случае очень сложно ответить на ваш вопрос, поскольку неясно, какая именно помощь вам нужна. http://stackoverflow.com/tour стоит прочитать. –
Добро пожаловать в StackOverflow. Прочтите и следуйте инструкциям по отправке в справочной документации. [по теме] (http://stackoverflow.com/help/on-topic) и [как спросить] (http://stackoverflow.com/help/how-to-ask) применяются здесь. StackOverflow не является кодовым или учебным сервисом. – Prune