最大递归，最大公约数

Question

我写了一个用Python找最大公约数的程序。

def gcd(a,b):
    r=a%b
    if r==0:
        return a
    elif r==1:
        return 1
    else:
        gcd(a,b)==gcd(b,r)
        return gcd(b,r)

每次我调用这个函数时，它都会显示“最大递归次数超出限制”的消息。请帮帮我。我知道可以用循环来实现，但我想特别用递归的方法来做。请多多包涵，我还是个学习者！

Answer 1

在编程中，有时候我们会遇到一些问题，特别是在使用某些工具或库的时候。这些问题可能会让我们感到困惑，不知道该怎么解决。比如，有人可能在使用某个特定的功能时，发现它并没有按照预期工作。这时候，查看其他人的经验和解决方案就显得特别重要。

在这个过程中，我们可以在一些技术论坛上找到很多有用的信息，比如StackOverflow。在那里，很多开发者会分享他们遇到的问题和解决办法。通过阅读这些内容，我们可以更好地理解如何处理类似的情况，避免走弯路。

总之，遇到问题时，不要害怕去寻求帮助，看看别人是怎么解决的，这样能让我们学到更多的知识。

def gcd(a,b):
    if a % b == 0:
       return b
    return gcd(b, a % b)

Answer 2

我就是这么做的

    def gcd(m,n):
      if m >= n:
      r = m % n
        if r == 0:
         return n
        else:
          m = n
          n = r
          return gcd(m,n)
      else:
        temp = m
        m = n
        n = temp
        return gcd(m,n)

Answer 3

gcd(a,b)==gcd(b,r) 并不是你想的那样。

它并不是说“把gcd(a,b)定义为等于gcd(b,r)”。

实际上，gcd(a,b)==gcd(b,r) 的意思是：

• 先计算 gcd(a,b)
• 再计算 gcd(b,r)
• 把这两个结果进行比较，看它们是否相等。

因为你在计算 gcd(a, b) 的时候又要用到 gcd(a, b)，这样就会陷入无限循环。

所以，你在那一步应该返回 gcd(b, r)。也就是说：

def gcd(a,b):
    r=a%b
    if r==0:
        return a
    elif r==1:
        return 1
    else:
        return gcd(b,r)

Answer 4

如果你想计算非常大的数字的最大公约数（比如在寻找RSA模数中的公共因子时），那么最好不要使用递归，而是用一个循环的方式来实现。比如：

def gcd(a,b):
    while a:
        a,b = b%a,a
    return b

Answer 5

这个语句是多余的，它导致了无限递归：gcd(a,b)==gcd(b,r)，因为它一直在重复调用gcd(a,b)。只需要把它去掉就行了：

def gcd(a,b):
    r=a%b
    if r==0:
        return a
    elif r==1:
        return 1
    return gcd(b,r)

顺便说一下，你的公式写错了。在条件语句中应该返回b，因为你在计算余数的时候是用a/b来进行的。

def gcd(a,b):
    r=a%b
    if r==0:
        return b
    elif r==1:
        return 1
    return gcd(b,r)

>>>gcd(10,4)
2