阶乘递归的调用栈：Factorial(4)

1. 第一次调用入栈

执行 Factorial(4) 时，系统为本次调用建立栈帧，保存参数 n=4、返回地址和现场信息。

Factorial(4)n=4

当前递归深度为 1。

int Factorial(int n) {
    if (n == 0) return 1;
    return n * Factorial(n - 1);
}

2. 递归体继续调用

n != 0，当前调用还不能返回；它要等待 Factorial(3) 的结果，所以新调用继续压栈。

Factorial(4)wait 4 *
Factorial(3)n=3

外层调用被挂起，控制权交给内层调用。

return 4 * Factorial(3);

3. 一直压到递归出口

每进入一层递归，就压入一个新的栈帧。到 n=0 时命中递归出口。

Factorial(4)wait
Factorial(3)wait
Factorial(2)wait
Factorial(1)wait
Factorial(0)return 1

栈顶是最后进入的调用。

if (n == 0) {
    return 1;
}

4. 出口返回，栈顶弹出

Factorial(0) 返回 1 后，它的栈帧被弹出，上一层 Factorial(1) 才能继续计算。

Factorial(4)wait
Factorial(3)wait
Factorial(2)wait
Factorial(1)1 * 1

返回顺序与调用顺序相反。

Factorial(1)
= 1 * Factorial(0)
= 1 * 1

5. 逐层恢复现场

每一层拿到内层返回值后，完成自己的乘法，再返回给更外层。

Factorial(4)wait
Factorial(3)wait
Factorial(2)2 * 1

Factorial(2) 返回后，Factorial(3) 才能继续。

Factorial(2) = 2 * 1 = 2
Factorial(3) = 3 * 2 = 6
Factorial(4) = 4 * 6 = 24

6. 最外层返回，调用栈清空

Factorial(4) 返回 24 后，最初的栈帧也被弹出，本次递归过程结束。

递归深度决定同时存在的栈帧数量。

// If each frame uses O(1) space:
space = O(recursion depth)