Python中如何实现最大公约数（gcd）

Question

我从 http://www.s-anand.net/euler.html 上拿了一段代码，问题5：

def gcd(a,b): 
    print a,b
    return b and gcd(b, a % b) or a

print gcd(10,20)

输出结果是：

10 20

20 10

10 0

10

为什么最后一行只打印了"a"，而不是"b"呢？

能不能解释一下上面代码中的return语句是怎么工作的？

我对"和"（and）和"或"（or）运算符有点困惑。

Answer 1

因为在你的例子中，10是最大公约数，比如gcd(10,20)的结果就是10。

你的代码（返回b和gcd(...)或者a）其实和下面这段是一样的：

def gcd(a,b): 
    print a,b
    if b:
        return b      
    else:
        res = gcd(b, a % b)
        return res if res else a

另外，注意在分数模块中还有一个gcd方法：

from fractions import gcd
print gcd(10,20)

Answer 2

Python中的and和or运算符使用了一种叫做短路求值的方式，刚开始可能会让人有点困惑。

如果把它们写成函数，可能会像这样工作，不过它们甚至不会计算右边的值，除非真的需要。

def and(left, right):
    if left:
        return right
    else:
        return left

def or(left, right):
    if left:
        return left
    else:
        return right

所以这一行return b and gcd(b, a % b) or a可以更详细地写成：

if b:
    temp_1 = gcd(b, a % b)
else:
    temp_1 = False

if temp_1:
    return temp_1
else:
    return a

如果你理清逻辑，这其实和找最大公约数的常见方法是一样的。不过，如果你对Python还不太熟悉，这段代码可能会让你觉得难以理解，所以你可能想避免使用这种写法。

Answer 3

b and gcd(b, a % b) or a

gcd(b, a % b) if b else a

这是以前写代码的方式：