如何计算最大公约数？

Question

这是我课本上的问题：

Greatest Common Divisor of two integers, p and q
(a) Base Case. If p = q: return p.
(b) p < q. If p < q: return GCD(q, p).
(c) p > q. If p > q: return GCD(p, p - q)

看起来我的解决方案和上面的描述是一样的。但是它出现了一个递归错误：

  File "G:\python\function.py", line 8, in GCD
    return GCD(p,p-q)
RuntimeError: maximum recursion depth exceeded

我的代码：

def GCD(p,q):
    """Greatest Common Divisor of two integers, p and q."""
    if q == p:
        return p
    elif p < q:
        return GCD(q,p)
    elif p > q:
        return GCD(p,p-q)
GCD(21,28)

难道我没有按照问题的描述来做吗？

Answer 1

最后一步应该对两个数中较小的那个进行取模运算。所以：

def GCD(p,q):
    """Greatest Common Divisor of two integers, p and q."""
    if p == q or q==0:
        return p
    elif p > q:
        return GCD(q,p) # ensure p < q
    return GCD(p,q%p) 
assert GCD(21,28) == 7
assert GCD(28,21) == 7
assert GCD(3,12) == 3
assert GCD(16,12) == 4