BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（初中组） 第 6 题

函数的递归和调用与下面哪个数据结构相关？

这题考递归的本质。拿到题先想：函数递归调用时，系统是怎么管‘谁在等谁’的？答案就是栈——先进后出，正好对应递归的压栈与出栈过程。

很多同学会凭直觉选二叉树，因为递归常用来遍历树，但那是应用层，不是底层机制；也有人选队列，觉得‘先进先出’像排队调用，其实递归是层层嵌套，必须后进先出才能正确返回。审题时别被‘递归’二字带偏，要抓住‘调用机制’这个核心词。

这道题考查的是函数调用与递归在计算机底层是如何实现的，核心知识点是‘栈’（Stack）及其‘先进后出’（LIFO）的特性。

在计算机运行程序时，每当一个函数被调用，系统就会在内存中开辟一块区域来保存这个函数的局部变量、参数以及最重要的——返回地址（即函数执行完后应该跳回去继续运行的位置）。这些保存下来的信息，就像把一张纸放进抽屉里一样，最晚放进去的最晚拿出来。这就是栈的工作原理。

递归函数更是如此。当函数 A 调用函数 A 时，系统需要先保存好外层 A 的上下文（包括那关键的返回地址），才能去执行内层的 A。只有当内层的 A 执行完毕，系统才会从栈顶弹出刚才保存的信息，回到外层 A 继续往下跑。这一进一出，完美对应了栈的压栈和出栈操作。如果换成队列（先进先出），那递归的层层嵌套就彻底乱了套，根本没法正确返回。

命题人挖坑的地方往往很隐蔽。他们喜欢用‘二叉树’、‘链表’这些和递归紧密相关的概念来混淆视听。比如看到递归，学生很容易联想到二叉树的遍历，从而误选 C。但题目问的是‘与哪个数据结构相关’，指的是实现机制，而不是应用场景。队列（A）和完全图（D）更是风马牛不相及，属于明显的干扰项。审题时要死死扣住‘调用机制’和‘返回顺序’这两个关键词，排除那些只是‘用了递归’但不是‘靠栈实现’的选项。

从考频趋势来看，BCSP-X 这类基础概念题在 2021-2024 年间出现频率稳定，尤其是‘栈与递归’、‘队列与 BFS'这种基础映射关系，几乎是必考点，2024 年再次出现第 6 题，说明命题组对基础概念的考察非常看重，不会轻易放过。

至于预测，基于近年真题的分布规律，未来几年继续考察‘数据结构与算法基础映射’的可能性极大，比如可能会问‘深度优先搜索（DFS）对应哪个数据结构’（答案依然是栈）或者‘广度优先搜索（BFS）对应哪个数据结构’（答案是队列）。这种基础概念的直接映射题，只要理解了本质，基本不会出错。