在递归函数中，我们需要在函数体中显式返回函数吗？

Question

我奉命用欧几里德方法找到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

你当然应该回电话。你知道吗

您正在执行一个返回某些内容的方法。在你的“else”中你什么也不回。你知道吗

Answer 2

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

从严格意义上讲，它并不是完全颠倒的，但我想我明白你的意思了。您可能希望在“子”调用之前打印“父”调用。你知道吗

但是，如果我们检查代码，就会发现：

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

如果您将两者互换，它将以您可能称之为“正确方式”的方式打印：

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的那一刻起就终止，因此如果在到达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的行的顺序相同。你知道吗