计算GCD时无法在if块中返回

Question

我正在尝试计算一个由2个数字组成的GCD，下面的代码块运行良好，我使用递归，但当我试图返回一个值时，我无法返回，return a会导致None

def gcd(a,b):
if b == 0:
print a
return a   # This is not working 
else:
gcd(b,a%b)
XX = gcd(3, 5)
print (XX)

输出：

1
None

Answer 1

您的代码

def gcd(a,b):
if b == 0:
print a
return a   # This is not working 
else:
gcd(b,a%b)
XX=gcd(3,5)
print (XX)

将不起作用，因为您在gcd(b,a%b)行中缺少return语句。所以应该是

def gcd(a,b):
if b == 0:
print a
return a
else:
return gcd(b,a%b)
print(gcd(12, 4))

顺便说一句，如果可能的话，不要自己编写代码，使用预定义的库：

from fractions import gcd
print(gcd(4, 12))

Answer 2

您的递归将不起作用。。。您缺少一个return语句，而且该算法也不起作用。。。

这就是递归gcd的样子：

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

这里是一个非递归的gcd:

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

还要注意，您可以只使用math.gcd。