algorithm - 帮我找出python中最大公约数算法的错误

Question

所以我写了

function gcd(a, b)
  if b <> 0
    gcd (b, a % b)
  else
    return a

print gcd (12, 9)

就这样：

1. gcd(12, 9)
2. 9 <> 0 表示真
3. gcd(9, 12 % 9 = 3)
4. 3 <> 0 表示真
5. gcd(3, 9 % 3 = 0)
6. 0 <> 0 表示错误
7. 返回 a 这是 3 但它什么也不返回

你能帮我找出我的错误吗？

Answer 1

我认为你需要这条线：

return gcd (b, a % b)

而不仅仅是：

gcd (b, a % b)

这是我的 Python 代码，显示了实际的解决方案：

>>> def gcd(a,b):
...   if b != 0:
...     return gcd(b, a % b)
...   else:
...     return a
...
>>> print gcd(12,9)
3
>>>

这是 Linux 上的 Python 2.4.3。