理解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

不过，一旦我有一对非零整数用与或逻辑进行比较时，我就搞不懂发生了什么以及为什么。

发生了什么呢？就是第一个影响结果的值会被返回。

x or y -> 当if x: 里的代码会执行时，它的结果是x，否则结果是y。

x and y -> 当if x: 里的代码不会执行时，它的结果是x，否则结果是y。

为什么会这样呢？因为GvR（Python的创始人）这么说的。这可能是为了让这个小技巧能正常工作，在x if C else y这个结构被加入语言之前。

不过，你知道的……你其实可以自己测试一下。这就是REPL（交互式解释器）的用处嘛 :)

Answer 2

在你的例子中，调用栈的情况是这样的：

gcf(42, 56)
gcf(56, 42) // 因为b不为零，所以会继续调用，并把42 % 56 (=42)作为第二个参数
gcf(42, 14) // 因为b不为零，所以会继续调用，并把56 % 42 (=14)作为第二个参数
gcf(14, 0) // 因为b不为零，所以会继续调用，并把42 % 14 (=0)作为第二个参数
return a // 因为b为零，所以直接返回a（14）

这个过程会一直回到最开始的调用。在Python中，and会返回数字而不是布尔值，这就是为什么最后返回结果是数字而不是1或true。

Answer 3

在Python中，布尔运算符'或'（or）和'与'（and）并不是返回布尔值（真或假），而是返回它们比较的其中一个值。

比如说，0 or n会返回的值。

而0 and n则会返回0。

另外，a and b or c其实是个小技巧，用来实现C语言中的(a ? b : c)这种写法。

想了解更多关于Python布尔运算和这个技巧的内容，可以看看Dive into Python的第4.6节。