Think Python Exercise 6.6

By Guanghao Zuo | April 16, 2023 | 1 minutes

编写一个叫 gcd 的函数，接受两个参数 a 和 b，并返回二者的最大公约数。

致谢：这道习题基于 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)

这样就很好了.