NOIP 提高组初赛 · NOIP 2008 提高组初赛试题 第 8 题

递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。

这题考递归调用的底层实现。拿到题先想：函数一层层嵌套，最里层的必须先处理完，外面的才能接着往下走。这种“后进先出”的次序，直接指向一种特定的数据结构。

学生容易把“数据结构”和“存储结构”搞混，看到递归就想到数组或链表，其实递归调用管理的是“状态”而非“数据”。队列是先进先出，和调用顺序完全相反；线性表、链表缺乏栈那种严格的“顶”操作，无法天然支持嵌套返回。最典型的坑是选错成队列或链表，没意识到“压栈 - 出栈”的 LIFO 特性才是关键。

递归调用为什么用栈？

考点与概念

这道题考查的是递归函数调用时，系统如何管理参数和返回地址。在计算机中，递归就是函数自己调用自己，一层套一层。比如算阶乘：fact(5) 会调 fact(4)，fact(4) 又调 fact(3)……直到 fact(1)。每一层调用都有自己的参数和要返回的地址，系统必须把这些信息保存起来，等最内层返回后，再一层层往外退。