面试题：C语言递归算法栈帧结构基础

Question

请简述在C语言递归函数调用过程中，栈帧是如何构建和销毁的？并且以一个简单的阶乘递归函数为例，画出每次递归调用时栈帧的大致结构。

Answer 1

1. 栈帧构建和销毁过程

• 构建：
  • 当一个函数（包括递归函数）被调用时，会在栈上为该函数分配一个新的栈帧。这个栈帧包含了函数的局部变量、参数、返回地址等信息。
  • 首先，调用者会将被调用函数的参数按照顺序压入栈中。然后，将返回地址（即调用函数后要继续执行的下一条指令的地址）压入栈。接着，被调用函数在栈上为自己的局部变量分配空间，构建好整个栈帧。
• 销毁：
  • 当被调用函数执行完毕，准备返回时，会先销毁自己的栈帧。
  • 先释放局部变量占用的空间，然后从栈中弹出返回地址，让程序跳转到调用函数的下一条指令继续执行，最后弹出参数占用的空间，栈帧完全销毁。

2. 阶乘递归函数示例及栈帧结构

#include <stdio.h>

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

假设调用 factorial(3)，栈帧结构如下：

• 初始调用 factorial(3)：

  • 栈帧1：
    • 参数：n = 3
    • 返回地址：调用 factorial(3) 之后的指令地址
    • 局部变量：无（尚未定义局部变量）

• 第一次递归调用 factorial(2)：

  • 栈帧2：
    • 参数：n = 2
    • 返回地址：factorial(3) 中乘法运算前的地址
    • 局部变量：无

• 第二次递归调用 factorial(1)：

  • 栈帧3：
    • 参数：n = 1
    • 返回地址：factorial(2) 中乘法运算前的地址
    • 局部变量：无

• 递归终止返回：

  • 栈帧3返回：factorial(1) 返回 1，栈帧3销毁。
  • 栈帧2继续执行：factorial(2) 计算 2 * 1，栈帧2销毁。
  • 栈帧1继续执行：factorial(3) 计算 3 * 2，栈帧1销毁，最终返回结果 6。