GESP 五级 · GESP 202509 C++ 五级 第 24 题

所有递归算法都可以转换为迭代算法。

递归问题关注两点：① 递归边界（终止条件）；② 递归关系（递推公式）。分析时展开前几步即可看出规律。

注意递归深度过大会导致栈溢出。递归必须包含终止条件，否则造成无限递归。

【考点】递归与迭代转换｜栈模拟｜函数调用机制

【考纲定位】这道题卡住的是对"递归本质"的误解——命题人专门把"所有递归都能转迭代"放在五级，就是看考生是否真的理解递归不过是函数调用栈的模拟过程。

【解题思维】递归调用时系统自动维护一个栈帧（参数、局部变量、返回地址），迭代实现时只要手动分配一个栈结构（struct StackFrame），在循环里 push 一个"下一步要递归调用的参数"，循环里 pop 一个栈帧，用 while 模拟递归的"返回"逻辑，就能完全等价。所以"所有递归都能转迭代"是成立的，答案选 A。

【陷阱拆解】错误选项 B 通常会让考生以为"递归有无限深度"或"某些特例无法模拟"，但题目说的是"所有"，命题人利用的就是"递归深度有限"这一细节——C++ 默认栈帧大小有限，但理论上只要栈空间够，任何递归都能被模拟；考试时考生容易忽略"理论上"和"实际栈溢出"的区别，掉进 B 里。

【反命题思维】如果改成"所有递归算法都能在 O(1) 额外空间下转换为迭代"，那就变成考"尾递归优化"或"栈空间复杂度"了，答案会翻转成错误。刷到类似题先问：命题人想考我"转换的可能性"还是"转换的成本"？