Think Python Exercise 6.6

编写一个叫 gcd 的函数,接受两个参数 ab,并返回二者的最大公约数。

致谢:这道习题基于 Abelson 和 Sussman 编写的 《Structure and Interpretation of Computer Programs》 其中的例子。

我的解答

算法是辗转相除法.

1
2
3
4
5
6
7
8
def gcd(a, b):
    a, b = (b, a) if a < b else (a, b)
    if b != 0:
        a, b = gcd(b, a % b)
    return a, b
    
result, _ = gcd(12,6)
print(result)

上面这个解答, 对递归理解得还不够.

1
2
3
4
5
6
def gcd(a, b):
    a, b = (b, a) if a < b else (a, b)
    return a if b == 0 else gcd(b, a % b)
    
result = gcd(12,6)
print(result)

这样就很好了.