在递归函数中，我们是否需要 return 在主体中显式地调用函数？

Question

我被指示使用 Euclid 方法找到 gcd。我最初在 Python 中写了以下内容：

def gcdRecur(a,b):
    if b==0:
        print('I am here')
        return a
    else:
        gcdRecur(b,a%b)
        print(a,b)

print(gcdRecur(51,187))

结果是：

I am here
34 17
51 34
187 51
51 187
None

我不知道为什么它的输出是这样的，然后我意识到看别人的代码是显式地使用 return 语句。

def gcdRecur(a,b):
    if b==0:
        print('I am here')
        return a
    else:
        return gcdRecur(b,a%b)
        print(a,b)


print(gcdRecur(51,187))

我得到了

I am here
17

所以我得到了我想要的，并且了解到我们应该使用 return 语句而不是仅仅调用函数。

我的问题是为什么第一段代码的输出是反的？为什么即使没有使用 return 语句，下面的代码也能工作

def tower(n,fr,to,spare):
    if n==1:
        print_move(fr,to)
    else:
        tower(n-1,fr,spare,to)
        tower(1,fr,to,spare)
        tower(n-1,spare,to,fr)

以上代码是我在edX上的麻省理工课程中学到的，是汉诺塔问题的解决方案。

这里的代码工作正常。所以当我想要以相反的顺序实现时，我们直接调用递归函数，并以正确的顺序使用 return 语句，对吗？

Answer 1

当然你应该 return 你的电话 return。

你正在做一个 return 的方法。在你"else"你return什么都没有。

Answer 2

My question is why is the output of the first code reversed?

在 strict 意义上并没有真正颠倒过来，但我想我明白你的意思了。您可能希望 "parent" 调用在 "child" 调用之前打印。

如果我们检查代码，我们会看到：

def gcdRecur(a,b):
    if b==0:
        print('I am here')
        return a
    else:
        gcdRecur(b,a%b)  # make child call
        print(a,b)       # print from the parent call

如果你交换了两者，它会打印出你可能称之为 "right way":

的内容

def gcdRecur(a,b):
    if b==0:
        print('I am here')
        return a
    else:
        # swap printing and recursive calls
        print(a,b)       # print from the parent call
        gcdRecur(b,a%b)  # make child call

但是，如果您使用 return 语句，函数会在到达 return 的那一刻终止，因此如果我们在 after return 语句已达到，打印永远不会发生。如果我们需要，我们可以使用 try-finally 结构。

更深入一点，如果我们“跟踪”一个程序，例如（这是不有效Python代码，更多的是深入了解这些调用是如何处理的）：

gcdRecur(51,187)
    if 187 == 0:  # fails
    else:  # we take the else branch
        gcdRecur(187,51)
            if 51 == 0:  # fails
            else:  # we take the else branch
                gcdRecur(51,34)
                    if 51 == 0:  # fails
                    else:  # we take the else branch
                        gcdRecur(34,17)
                            if 51 == 0:  # fails
                            else:  # we take the else branch
                                gcdRecur(17,0)
                                    if 0 == 0:  # succeeds!
P                                       print('I am here')
                                        return 17
P                               print(34,17)
P                       print(51,34)
P               print(187,51)
P       print(51,187)

我在这里用 P 标记了 print 的行。如您所见，带有 P 的行的顺序相同。

在递归函数中，我们是否需要 return 在主体中显式地调用函数？

In recursive functions do we need to return the function explicitly in the body?

python

recursion

return

greatest-common-divisor