4. 递归与栈帧

好，咱们今天来聊一个非常核心的话题——递归调用时，栈帧到底是怎么创建和销毁的。

说实话，我刚开始学递归的时候，总觉得这玩意儿很玄乎。函数调用自己？那内存里到底发生了什么？会不会乱套？

后来我亲手画了几次栈帧变化图，才彻底搞明白。嗯，今天我就用 factorial(5) 这个经典例子，带你一步步走一遍。

1. 什么是栈帧？

先简单说一下概念。每个函数调用，系统都会在调用栈上分配一块内存区域，这块区域就叫栈帧。

栈帧里存了啥？说白了就是：

• 函数的参数
• 局部变量
• 返回地址（函数执行完后该回到哪）
• 一些寄存器状态

你想想看，每次调用函数，系统就往栈上压一个帧。函数返回，就弹出这个帧。这就是栈帧的创建与销毁。

2. factorial(5) 的递归过程

先看代码：

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

result = factorial(5)
print(result)  # 输出 120

这个函数很简单，但它的栈帧变化过程，值得你仔细琢磨。

3. 逐步分析栈帧变化

咱们从 factorial(5) 开始，一步步看。

第1步：调用 factorial(5)

系统创建第一个栈帧，参数 n = 5。此时 n != 1，所以进入 else 分支，需要计算 5 * factorial(4)。

但 factorial(4) 还没算出来，所以这个栈帧不能销毁，得等着。

第2步：调用 factorial(4)

系统在栈上压入第二个栈帧，参数 n = 4。同样，需要 4 * factorial(3)，继续等待。

第3步：调用 factorial(3)

压入第三个栈帧，n = 3。等待 3 * factorial(2)。

第4步：调用 factorial(2)

压入第四个栈帧，n = 2。等待 2 * factorial(1)。

第5步：调用 factorial(1)

压入第五个栈帧，n = 1。这次不一样了——n == 1，直接返回 1。

好，到这里，栈上已经压了5个帧。我画个图给你看：

4. 栈帧的销毁过程（回溯）

现在开始回溯阶段。这是栈帧销毁的过程。

第1步：factorial(1) 返回

factorial(1) 返回 1，它的栈帧被弹出（销毁）。控制权回到 factorial(2)。

第2步：factorial(2) 计算并返回

factorial(2) 拿到 factorial(1) 的结果 1，计算 2 * 1 = 2，返回 2。它的栈帧被销毁。

第3步：factorial(3) 计算并返回

拿到 2，计算 3 * 2 = 6，返回 6。栈帧销毁。

第4步：factorial(4) 计算并返回

拿到 6，计算 4 * 6 = 24，返回 24。栈帧销毁。

第5步：factorial(5) 计算并返回

拿到 24，计算 5 * 24 = 120，返回 120。最后一个栈帧销毁。

整个过程，栈帧就像叠盘子——先叠上去，再一个个拿下来。这就是后进先出（LIFO）的典型表现。

5. 核心要点总结

阶段	栈帧数量	栈顶内容	说明
递推开始	1	factorial(5)	第一个栈帧创建
递推中间	5	factorial(1)	栈帧达到最多，深度为5
回溯开始	4	factorial(2)	factorial(1) 已返回，栈帧销毁
回溯结束	0	无	所有栈帧销毁，返回最终结果

6. 避坑指南

• 不要忘记终止条件：没有终止条件，递归会无限进行，栈帧无限创建，最终栈溢出。
• 注意递归深度：Python 默认递归深度限制是 1000 左右。你可以用 sys.setrecursionlimit 调整，但不建议调太大。
• 尾递归优化：有些语言（如 Scheme）支持尾递归优化，可以复用栈帧。但 Python 不支持，所以别指望这个。

我个人习惯是：递归深度超过 100 的，我都会考虑用迭代重写。你想想看，万一哪天数据量翻倍，程序突然崩了，那多尴尬。

7. 小结

递归调用时，栈帧的创建与销毁，说白了就是递推时压栈，回溯时弹栈。每个栈帧保存了函数的参数和局部变量，直到内层调用返回后才释放。

理解这个过程，对你调试递归代码、分析性能瓶颈、甚至理解操作系统原理都很有帮助。嗯，今天就到这里，希望你能亲手画一画栈帧变化图，效果比光看要好得多。

---