调用栈与递归深度

学习目标

本节学习递归背后的执行过程：调用栈。

很多初学者能写出递归代码，但不清楚程序实际如何一步步执行。理解调用栈后，你会知道为什么递归会返回上一层，为什么递归太深会出错，以及为什么递归也会带来空间成本。

---

什么是调用栈

当一个函数被调用时，程序需要保存这个函数的局部变量、参数和返回位置。多个函数嵌套调用时，这些信息会按照后进先出的方式保存，这个结构称为调用栈。

递归函数不断调用自己，本质上就是不断向调用栈中压入新的函数调用记录。

当最深层函数返回后，调用栈再一层一层弹出，程序回到上一层继续执行。

---

阶乘调用过程

以 factorial(4) 为例：

factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1

调用过程可以理解为先不断向下展开，直到遇到递归出口；然后再从出口开始一层一层返回结果。

1. 调用 factorial(4)，它需要等待 factorial(3) 的结果。

2. 调用 factorial(3)，它需要等待 factorial(2) 的结果。

3. 调用 factorial(2)，它需要等待 factorial(1) 的结果。

4. factorial(1) 命中递归出口，直接返回 1。

5. factorial(2) 得到结果后返回 2。

6. factorial(3) 得到结果后返回 6。

7. factorial(4) 得到结果后返回 24。

---

递归深度

递归深度指的是递归调用最多同时存在多少层。

对于 factorial(n)，递归深度大约是 $n$，因为它会从 $n$ 一直递归到 1。

递归深度会影响空间复杂度。即使函数没有额外创建数组，每一层调用也会占用调用栈空间。因此，阶乘递归的额外空间复杂度通常是 $O(n)$。

---

递归太深会发生什么

如果递归深度过大，调用栈可能耗尽，程序就会出现栈溢出或递归深度错误。

下面是一个没有正确出口的递归示例：

C++

void infiniteRecursion() {
    infiniteRecursion();
}

Java

void infiniteRecursion() {
    infiniteRecursion();
}

Python

def infinite_recursion():
    infinite_recursion()

C#

void InfiniteRecursion()
{
    InfiniteRecursion();
}

这段代码没有停止条件，会不断调用自己。真实程序中应避免这种递归。

---

调用栈与栈结构的联系

上一章学习过栈。调用栈正是栈思想在程序运行时的体现。

函数调用时，相当于把调用记录压入栈；函数返回时，相当于把调用记录弹出栈。最后调用的函数最先返回，这正好符合后进先出规则。

因此，理解栈之后再理解递归，会更容易看清递归执行过程。

---

本节小结

递归调用会在调用栈中保存每一层函数调用记录。

递归深度会影响空间复杂度，深度过大可能导致栈溢出。分析递归时，不仅要看时间复杂度，也要看递归深度带来的额外空间成本。