GESP 五级 · GESP 202603 C++ 五级 第 25 题

任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。

仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】递归的本质｜迭代转递归的栈模拟｜二叉树遍历

🎯 考纲定位：五级算法模块，考察递归本质与迭代转递归的栈模拟。命题人想卡住考生对递归调用机制的深层认知：很多人以为"递归=栈"，却忽略了栈只是模拟递归的一种手段，并非唯一手段。

🧠 解题思维：核心观察——递归调用过程天然依赖系统栈，但改写为迭代时，可以用显式栈模拟，也可以用队列模拟（如二叉树层次遍历）。因此"一定需要显式栈"是绝对化错误。

🪤 陷阱拆解：A项陷阱在于"等价非递归程序"是成立的，但B项的"一定需要显式栈"是命题人抛出的绝对化表述。如果你只背"递归转迭代要栈"这个结论，就会掉进这个陷阱。实际上，二叉树的前序、中序、后序遍历都可以用队列模拟，不需要显式栈。

🔄 反命题思维：如果把题目改成"任何二叉树遍历都可以用队列模拟"，答案就变成正确。这类题的关键是识别绝对化表述（"一定""必须"）并寻找反例。