递归实现斐波那契序列时，print语句位置为何会改变输出顺序？

这是个特别经典的递归理解问题，核心就在于搞懂递归调用栈的「前进」和「回溯」两个阶段的执行时机——咱们一步步拆解两种写法的执行流程，就能瞬间明白差异所在。

所有递归函数的执行都分为两步：

• 前进阶段：不断调用自身，直到触发终止条件（也就是代码里的i==x），这个过程就像往栈里一层层压函数调用；
• 回溯阶段：从最深层的函数调用开始，依次返回上一层，执行每个函数调用点之后的代码，这个过程就像把栈里的函数调用一层层弹出来。

方法1：Print在递归调用之后（逆序输出） #

先看代码：

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)  # 递归调用先执行，这是「前进阶段」的核心
        # 这行代码要等递归调用完全结束才会执行！属于「回溯阶段」
        print(c,a,i)
        return i # not the Fibonacci number

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

执行流程拆解 #

当x=6时：

1. 前进阶段：函数会从i=0一路调用到i=6，这期间只会执行c=a+b、变量赋值和递归调用，完全不会碰print(c,a,i)；
2. 触发终止条件：i=6时，打印21 first print statement，然后开始回溯；
3. 回溯阶段：从i=5的函数调用开始，依次执行每个递归调用点之后的print：
   • 回到i=5：打印13 8 5
   • 回到i=4：打印8 5 4
   • ...直到回到i=0，执行完print后返回i=0，最后打印0 final print statement

所以输出顺序是先最大的数（21），再依次打印回溯过程中更小的数，也就是逆序。

方法2：Print在递归调用之前（正序输出） #

再看代码：

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:
        # 先打印当前a的值，这是「前进阶段」就执行的代码
        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]

执行流程拆解 #

当x=6时：

1. 前进阶段：每进入一层递归，先执行print(a,i)，再进行递归调用：
   • i=0：打印0 0，然后调用i=1的递归
   • i=1：打印1 1，然后调用i=2的递归
   • ...直到i=6，打印13 first print statement
2. 回溯阶段：因为递归调用之后没有print语句，所以直接逐层返回，最后打印0 last print statement

所以输出顺序是从最小的数开始，随着递归前进依次打印，也就是正序。

核心差异总结 #

两种写法的本质区别，就是print语句属于递归的哪个阶段：

• 方法1的print在递归调用之后，属于「回溯阶段」执行的代码——只有当深层递归完全结束后才会触发，所以输出顺序是从深层到浅层（逆序）；
• 方法2的print在递归调用之前，属于「前进阶段」执行的代码——每进入一层递归就立刻打印当前值，所以输出顺序是从浅层到深层（正序）。

你之前疑惑的“输出顺序应该一致”，是混淆了递归的前进和回溯阶段：递归栈出栈时执行的是调用点之后的代码，而调用点之前的代码是在入栈时就执行了，两者的时机完全不同。

内容的提问来源于stack exchange，提问作者ray_milan