递归GCD不返回预期结果

Question

Python中的这个函数是递归地找到2个整数的最大公约数。但我没有得到它的工作，因为它应该在测试

def gcdRecur(a, b): 
    if a > b: 
     (a,b) = (b,a) 
    if b%a == 0: 
     #print("b%a == 0") 
     print ("a is " + str(a)) 
     return a 
    else: 
     gcdRecur(b%a,b) 



print("gcdRecur(45, 42) " + "should be 3, and we got " + str(gcdRecur(45, 42))) 
print("gcdRecur(6, 12) " + "should be 6, and we got " + str(gcdRecur(6, 12))) 
print("gcdRecur(12, 16) " + "should be 4, and we got " + str(gcdRecur(12, 16))) 
print("gcdRecur(17, 12) " + "should be 1, and we got " + str(gcdRecur(17,12))) 

Answer 1

像我的评论说的。您在else声明中缺少return。

else: 
    return gcdRecur(b%a,b) 

您需要返回语句，因为您需要链接递归返回。使用Sven Marnach的功能可以在这里找到：https://stackoverflow.com/a/5537507/4099813

我们可以采取跟踪函数Sven写道，看看发生了什么，以及为什么你需要返回语句。 （我们需要修改自己的功能，接受多个参数：

def trace(f): 
    indent = 0 
    def g(*x): 
     nonlocal indent 
     print('| ' * indent + '|--', f.__name__, x) 
     indent += 1 
     value = f(*x) 
     print('| ' * indent + '|--', 'return', repr(value)) 
     indent -= 1 
     return value 
    return g 

def gcdRecur(a, b): 
if a > b: 
    (a,b) = (b,a) 
if b%a == 0: 
    return a 
else: 
    gcdRecur(b%a,b) 

gcdRecur = trace(gcdRecur) 

gcdRecur(45,42) 

跑的时候，它给我们带来哪些：

|-- gcdRecur (45, 42) 
| |-- gcdRecur (3, 45) 
| | |-- return 3 
| |-- return None 

注意它返回无因为你没有说明它应该返回的值是发现在递归的下一级

添加return到else声明将产生：

|-- gcdRecur (45, 42) 
| |-- gcdRecur (3, 45) 
| | |-- return 3 
| |-- return 3