为什么在斐波那契模式中，在递归中，通过改变打印语句的位置，输出的顺序会改变？

Question

第一个方法中，在else块中，在递归调用下面有一个对print函数的调用。因此我们获得了斐波那契数列，但顺序相反（从大到小）。

# method 1
def fib(a,b,c,i,x):
    if i==x:
        c = a+b
        # first print statement       [21]
        print(c, "first print statement")           
        return c                    # c = 21, returns to the function itself
    else:
        c = a+b
        a = b
        b = c
        fib(a,b,c,i+1,x)
        # recursive print statements  [13,8,5,3,2,1]
        print(c,a,i)
        return i                    # not the Fibonacci number

# final print statement               [0]
print(fib(0,1,1,0,6), "final print statement")

在第二种方法中，我们得到相同的斐波那契形态，但这次是按原始顺序（从小到大）。

# method 2
def fib(a,b,c,i,x):
    if i==x:
        c = a+b
        # first print statement       [21]
        print(a, "first print statement")
        return c                    # c = 21, returns to the function itself
    else:
        # recursive print statements  [1,2,3,5,8,13]
        print(a,i)
        c = a+b
        a = b
        b = c
        fib(a,b,c,i+1,x)          
        return i                    # not the Fibonacci number

print(fib(0,1,1,0,6),"last print statement")               # final print statement                        [0]

唯一的区别是 print 语句被移至 else 块的最开头。

这怎么可能？

如何通过改变打印语句的位置来改变整个顺序？

我们知道，在递归中，当堆栈下降时，值会从内存中出来，并打印输出（从堆栈深度存在的较大值到最小值）。

因此，两种条件下打印输出的顺序应该保持相同，不是吗？

请帮助我了解，更改 else 块中 print 语句的位置如何改变输出顺序。

Answer 1

您的推理是正确的，但是考虑到您在第一个方法中执行的每个递归调用（调用 fib 后打印），您将首先进行递归，直到达到退出条件。这将打印“第一个打印语句”，然后，它将在使用最后计算值调用 fib 后执行打印。然后我们向上递归层，从而反向打印斐波那契数列。

一种观察方式是想象一个盒子在另一个盒子里面。在调用 fib 之后的 print 中，您将从最后一个值打印到第一个值，在调用之前的 print 中，您将从第一个值打印到最后一个值。

您可以尝试这个演示递归级别的小程序：

def recursive_function(level):
    if level >= 5:
        print('[ Level', level, ']-You reached the bottom of the call stack. Time to go back up in reverse')
    else:
        print('[ Level', level, ']-I get printed first and then you move down to level', level+1, 'of the call stack')
        recursive_function(level+1)
        print('[ Level', level, ']-I won\'t get printed unless you return from the level', level+1)

if __name__ == '__main__':
    recursive_function(0)

打印：

[ Level 0 ]-I get printed first and then you move down to level 1 of the call stack
[ Level 1 ]-I get printed first and then you move down to level 2 of the call stack
[ Level 2 ]-I get printed first and then you move down to level 3 of the call stack
[ Level 3 ]-I get printed first and then you move down to level 4 of the call stack
[ Level 4 ]-I get printed first and then you move down to level 5 of the call stack
[ Level 5 ]-You reached the bottom of the call stack. Time to go back up in reverse
[ Level 4 ]-I won't get printed unless you return from the level 5
[ Level 3 ]-I won't get printed unless you return from the level 4
[ Level 2 ]-I won't get printed unless you return from the level 3
[ Level 1 ]-I won't get printed unless you return from the level 2
[ Level 0 ]-I won't get printed unless you return from the level 1