Понимание реализации алгоритма Евклида для GCF в Python

Question

Алгоритм Евклида для GCF двух чисел: GCF(a, b)=GCF(b, a mod b). Я видел это реализовано в Python следующим образом:

def gcf(a, b):
    return b and gcf(b, a%b) or a

Я не понимаю, как анализировать эту функцию или, в частности, как логическая логика применяется к целым числам. Например, gcf(42, 56) = 14. Когда я прохожу через него, я вижу, что в конечном итоге рекурсивная часть возвращает ноль. Я следую этому 0 or n == n и 0 and n == 0. Однако, как только я сравниваю пару ненулевых целых чисел с и / или логикой, я не понимаю, что происходит и почему.

Может ли кто-нибудь провести меня через эту функцию?

Answer 1

Python логические операторы 'or' и 'и' не возвращают логические значения. Они возвращают одно из сравниваемых значений.

0 или n - возвращает n

0 и n - возвращает 0

a and b or c - это просто хитрость для реализации синтаксиса (a ? b : c) в C.

Прочтите раздел 4.6 Погружение в Python , чтобы получить подробное описание логических операций Python и этого трюка.

Answer 2

Однако, когда у меня есть пара ненулевых целых чисел, сравниваемых с и / или логикой, я не понимаю, что происходит и почему.

Что случается так, что возвращается первое значение, которое влияет на результат.

x or y -> оценивается как x всякий раз, когда выполняется код в блоке if x:, а в противном случае оценивается как y.

x and y -> оценивается как x всякий раз, когда код в блоке if x: будет не выполняться, а в противном случае оценивается как y.

Почему это происходит, потому что GvR так сказал.Возможно, возможно, именно этот трюк и работал, еще до того, как в язык была добавлена ​​конструкция x if C else y.

Но, вы знаете ... Вы могли бы просто проверить это для себя.Вот для чего нужен REPL:)

Answer 3

В вашем случае стек вызовов будет выглядеть так:

gcf (42, 56)
gcf (56, 42) // так как b было ненулевым, рекурсивно и передаст 42% 56 (= 42) в качестве второго аргумента
gcf (42, 14) //, так как b был ненулевым, будет повторяться и передавать 56% 42 (= 14) в качестве второго аргумента
gcf (14, 0) // так как b было ненулевым, рекурсивно и передаст 42% 14 (= 0) в качестве второго аргумента
вернуть //, так как b был равен нулю, просто вернет a (14)

Это выскочит до самого верха. В python и возвращает номер, а не логическое значение, поэтому всплывающее окно возвращает результат, а не 1 / true.

Answer 4

Если b не равно нулю, то результатом будет gcf (b, a% b) (recurse). Если b равно нулю, то результат a.