[已解决]递归求欧几里得算法

CarterZhang

自己写了一个，请大佬们过目：
def gcd(x,y):
    if y == 0 or x == 0:
        return 0
    else:
        return gcd(y,x%y)

x = int(input("1:"))
y = int(input("2:"))
print(gcd(x,y))

无论输入什么，都返回0。问题是不是出在if的return 0上？
如果是，那x和y都不等于0的话会执行else呀？求解答!

最佳答案

月排行榜 / 总排行榜

jackz007

2020-11-19 11:39:15

def gcd(x , y):
    if y == 0:
        return x
    else:
        return gcd(y , x % y)
x , y = map(int , input() . split())
print(gcd(x , y))

跳转到最佳答案楼层

jackz007

def gcd(x , y):
    if y == 0:
        return x
    else:
        return gcd(y , x % y)
x , y = map(int , input() . split())
print(gcd(x , y))

CarterZhang

jackz007 发表于 2020-11-19 11:39

大佬，能解答一下为什么if条件里面return不能是0嘛?

lirenbing01

CarterZhang 发表于 2020-11-20 10:40
大佬，能解答一下为什么if条件里面return不能是0嘛?

你if y == 0 or x == 0: 是你期望的递归出口
return 0 当然输出也是0

jackz007

CarterZhang 发表于 2020-11-20 10:40
大佬，能解答一下为什么if条件里面return不能是0嘛?

        辗转相除法终止的条件是除数为 0，结果是这个时候的被除数。所以，递归是否到达终点，只需判断除数是否为 0 就可以了。