递归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)

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

我们可以使用Sven编写的跟踪函数，看看发生了什么以及为什么需要return语句。（我们需要修改他的函数以接受多个参数：

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

注意，它返回None是因为您没有声明它应该返回在下一级递归中找到的值？你知道吗

将return添加到else语句将产生：

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