每日科普 · 2026-11-06 周五

考研 408 × 求职面试

知识点 · 数据结构 · 进阶

栈与递归的实现及递归工作栈

栈是只能在一端插入和删除的线性表，遵循后进先出。递归函数在执行中会调用自身，程序必须记住每一层“返回到哪里、参数和局部变量是什么”，这些信息由系统用递归工作栈保存。每次调用生成一个栈帧，压入参数、返回地址、局部变量等；遇到递归出口后逐层返回，每返回一层就弹出并恢复对应栈帧。因此递归的执行轨迹可看作：压栈深入，到出口后出栈回溯。递归深度就是同一时刻栈中活动栈帧的数量；深度过大可能栈溢出。把递归改写成非递归时，常需自己用栈模拟这些栈帧。理解这一点，就能从“函数调用—栈帧—返回”角度分析递归过程。

每日一题 · 数据结构

栈与递归的实现及递归工作栈

下列关于递归工作栈的说法，正确的是（ ）。A. 递归工作栈遵循先进先出 B. 每次递归调用会把返回地址、实参和局部变量等信息压入栈帧 C. 递归返回时不需要恢复各层局部变量 D. 递归深度不会影响栈空间使用

解析

选B。每次调用形成栈帧，保存返回地址、实参、局部变量等，返回时弹栈恢复。A错，递归工作栈是后进先出；C错，返回时必须恢复现场；D错，递归越深占用栈空间越大，可能栈溢出。

面试小贴士 · 数据结构

栈与递归的实现及递归工作栈

面试常问递归如何借助栈实现、栈帧存什么、递归深度与溢出。答题时按“调用压栈—出口回溯—返回弹栈”说明，并现场画图。易错：说成队列、漏掉返回地址、误认为递归一定更快。

代码实现 · C

代码示例

#include <stdio.h>

int fact(int n) {
    if (n == 0) return 1;         // 递归出口
    return n * fact(n - 1);       // 调用时压入新栈帧
}

int main(void) {
    int n = 5;
    printf("fact(%d)=%d\n", n, fact(n)); // 返回时逐层弹栈
    return 0;
}