递归的调用过程——就像倒放录像带

递归的调用过程：像倒放录像带一样理解函数调用

上一节我们知道了递归函数会调用自己。但计算机在执行时，到底是怎么工作的呢？为什么递归函数能一层层深入，最后又能一层层返回？我们可以把递归的调用过程想象成倒放录像带：先快速前进（调用），然后倒带（返回）。这个过程就像你按下录像机的“前进”键，然后又按下“倒放”键，画面会按相反的顺序出现。

理解递归的调用过程，能帮你真正掌握递归的精髓，避免写出无限循环或逻辑混乱的递归代码。

什么是“栈”？——计算机里的“叠盘子”

计算机用一块叫做“栈”的内存区域来记录函数调用。栈就像一个叠盘子的架子：每次你调用一个函数，计算机就会把一个新“帧”（记录函数当前的状态，比如参数、局部变量）放在栈的最上面（就像往架子上放一个新盘子）。当函数执行完毕返回时，最上面的帧被拿走（就像把盘子拿走）。这个结构叫做“后进先出”（LIFO）：最后放上去的帧最先被拿走。

在递归中，每次函数调用自己，就会在栈上叠一个新帧。调用越深，栈就越高。当达到终止条件后，函数开始返回，栈就从最上面一层层“拆掉”。

生活中的例子：排队买东西

假设你去超市买零食，排队结账。队伍很长，你前面有3个人。如果你要算总价，可以这样递归地思考：

第3个人（最后一个人）看到前面有2个人，他问前面的人“你们总共多少钱？”然后等回答。
第2个人又问他前面的人……直到第1个人（最前面）直接知道自己的价格（终止条件）。
第1个人报出价格，第2个人加上自己的价格，传回给第3个人，最后你得到总价。

这里的“问前面的人”就像递归调用，等待回答就像把函数调用压入栈，而回答就像函数返回并弹出栈。

用一个例子看透调用过程

我们用倒计时函数来演示：countdown(3) 应该打印 3, 2, 1，然后在返回时再打印“返回了”信息。这样你就能清楚看到调用和返回的顺序。

def countdown(n):                # n: 倒计时起始数字
    if n == 0:                   # 终止条件
        return                   # 当n=0时，不再调用，直接返回
    print(n)                     # 打印当前数字
    countdown(n - 1)             # 递归调用，数字减1
    print("返回了", n)           # 这一行在递归返回后才执行

countdown(3)                     # 从3开始倒计时

运行这段代码，输出是：

3
2
1
返回了 1
返回了 2
返回了 3

为什么“返回了”的打印顺序和数字顺序相反？接下来我们一步步拆解。

我们一步步拆解——看栈的变化

为了更直观，我们把每一步的栈状态用文字画出来。栈的底部是第一个函数，顶部是最后一个。

第1步：`countdown(3)` 开始

n=3，不等于0，打印 3。
遇到 countdown(2)，暂停当前函数（记住：它还没执行完，还有一行 print("返回了", 3) 等着呢）。
把 countdown(3) 的帧放到栈底（暂时忽略具体数据，只记调用顺序）。
栈现在：[countdown(3)]

第2步：`countdown(2)` 运行

n=2，打印 2。
遇到 countdown(1)，暂停，把 countdown(2) 的帧叠上去。
栈：[countdown(3), countdown(2)]

第3步：`countdown(1)` 运行

n=1，打印 1。
遇到 countdown(0)，暂停，把 countdown(1) 的帧叠上去。
栈：[countdown(3), countdown(2), countdown(1)]

第4步：`countdown(0)` 运行

n=0，满足终止条件，直接 return，函数结束。
此时 countdown(0) 的帧被弹出（拿走）。
栈：[countdown(3), countdown(2), countdown(1)]（注意：最上面是 countdown(1) 的帧，它之前被暂停了）

第5步：回到 `countdown(1)` 继续

刚才 countdown(1) 执行到 countdown(0) 之后，现在继续执行下一行：print("返回了", 1)，打印 返回了 1。
函数执行完毕，弹出 countdown(1) 的帧。
栈：[countdown(3), countdown(2)]

第6步：回到 `countdown(2)` 继续

执行 print("返回了", 2)，打印 返回了 2。
函数结束，弹出帧。
栈：[countdown(3)]

第7步：回到 `countdown(3)` 继续

执行 print("返回了", 3)，打印 返回了 3。
函数结束，弹出帧，栈变空。
整个递归过程结束。

你会发现“返回了”的打印顺序和调用顺序正好相反——这就是“倒放录像带”的感觉。理解了这个过程，你就知道递归函数是如何一步步展开的了。

新手容易犯的错误

忘记写终止条件
如果 countdown 函数里没有 if n == 0: return，那它会无限调用自己，最终导致“栈溢出”错误（就像叠盘子叠得太高，架子倒了）。
```
def countdown(n):
    print(n)
    countdown(n - 1)  # 没有终止条件，永远不停止
```
运行后会报 RecursionError: maximum recursion depth exceeded。
终止条件写错
比如把 if n == 0: 写成 if n <= 0:，可能导致递归多走一层或提前返回。
或者把 return 写成了 return n，但函数本不需要返回值，却返回了一个值，可能干扰后续逻辑。
把递归调用放在停止条件之前
如果你先打印“返回了”再递归，逻辑会乱。比如：
```
def countdown(n):
    print("返回了", n)  # 先打印
    if n == 0:
        return
    countdown(n - 1)
```
结果会先打印“返回了 3, 返回了 2, 返回了 1, 返回了 0”，完全不是倒计时效果。记住：递归调用前的代码在“前进”时执行，调用后的代码在“返回”时执行。
混淆参数的变化
递归调用时参数的传递方向要清楚。比如 countdown(n - 1) 是减少1，如果你写成 countdown(n + 1)，会离终止条件越来越远，变成无限递归。

完整可运行示例：用递归求 1 到 n 的和

为了更全面理解递归调用过程，我们再看一个例子：计算 1 + 2 + 3 + ... + n。这个函数的返回值会一层层传递回来，就像刚才倒计时例子中的“返回了”信息，只不过这次我们传递的是数值。

def sum_n(n):                     # n: 要加到的最大数字
    if n == 1:                    # 终止条件：1加到1等于1
        return 1
    return n + sum_n(n - 1)       # 当前数字加上前面数字的和

result = sum_n(5)                 # 计算1+2+3+4+5
print("1到5的和是：", result)     # 输出15

调用过程拆解（用栈理解）

sum_n(5) 调用 sum_n(4)，自己等待
  sum_n(4) 调用 sum_n(3)，自己等待
    sum_n(3) 调用 sum_n(2)，自己等待
      sum_n(2) 调用 sum_n(1)，自己等待
        sum_n(1) 返回 1   （终止条件）
      sum_n(2) 返回 2 + 1 = 3
    sum_n(3) 返回 3 + 3 = 6
  sum_n(4) 返回 4 + 6 = 10
sum_n(5) 返回 5 + 10 = 15

最终结果 15 就是通过这样一层层返回累加得到的。注意，这里的返回顺序仍然是“倒放”，和刚才的打印例子完全一致。