[已解决]关于递归求最大公约数的问题，大佬请指教

skhzhuanqian

def gcd(x, y):
    if y:
        return gcd(y, x%y)
    else:
        return x
print(gcd(4, 8))

这个是鱼C的答案，完美运行；

def gcd(x, y):
    if x:
        return gcd(x, y%x)
    else:
        return y
print(gcd(4, 8))

如上，我把x和y位置调换了，就报错，请问是什么原因呢？

最佳答案

月排行榜 / 总排行榜

zltzlt

2019-8-16 22:31:14

你的函数是这样：

1. def gcd(x, y):
   
2.     if x:
   
3.         return gcd(x, y%x)
   
4.     else:
   
5.         return y

复制代码

当 gcd(4, 8) 时，x = 4，y = 8。x 为真，返回 gcd(4, 0 (8 % 4))。当 gcd(4, 0) 时， x = 4，y = 0。x 为真，返回 gcd(4, 0 (0 % 4))。这样 x 永远也不可能有假的机会，所以报递归错误。

跳转到最佳答案楼层

zltzlt

你的函数是这样：

1. def gcd(x, y):
   
2.     if x:
   
3.         return gcd(x, y%x)
   
4.     else:
   
5.         return y

复制代码

当 gcd(4, 8) 时，x = 4，y = 8。x 为真，返回 gcd(4, 0 (8 % 4))。当 gcd(4, 0) 时， x = 4，y = 0。x 为真，返回 gcd(4, 0 (0 % 4))。这样 x 永远也不可能有假的机会，所以报递归错误。

jackz007

        你这么改的理由是什么？写程序要求的是逻辑严谨，不是搞文学创作！

skhzhuanqian

jackz007 发表于 2019-8-16 22:43
你这么改的理由是什么？写程序要求的是逻辑严谨，不是搞文学创作！

x,y没有限定哪个大哪个小嘛，所以就想如果原答案的参数是前小后大的话，按照答案那么写可行，
那如果参数是前大后小呢？调换一下后面的x，y位置应该也是对的啊，结果就报错了。。

jackz007

       gcd(x , y) 如果 x < y，那么，x % y = x，下一步递归的时候，return gcd(y , x % y) 首先实现的就是 x、y 位置的对调。这正是本算法精妙之处，调用函数时，两个输入参数不要求顺序。

skhzhuanqian

jackz007 发表于 2019-8-16 23:39
gcd(x , y) 如果 x < y，那么，x % y = x，下一步递归的时候，return gcd(y , x % y) 首先实现的就 ...

受教了，感谢大佬