含递归后执行语句的递归函数转迭代函数的实现问题

你的问题核心在于：递归函数中递归调用语句之后还有需要执行的代码（输出break），而普通栈仅存储函数参数的方式无法记录当前的执行进度——不知道是刚进入函数要执行前半部分，还是从递归返回后要执行后续的break输出。

要解决这个问题，我们需要让栈存储执行状态，而不是单纯的参数。状态需要包含：当前函数的参数x，以及当前循环的迭代进度i（用来标记是刚进入函数，还是已经完成了第i次递归调用、需要执行后续步骤）。

具体实现步骤 #

1. 定义栈元素的状态结构，用来记录当前的执行位置：

struct StackFrame {
    int x;
    int i; // -1表示刚进入函数，需要执行开头逻辑；i>=0表示已完成第i次递归，需执行break并继续循环
    StackFrame(int x_, int i_) : x(x_), i(i_) {}
};

2. 修改迭代函数fIterative，基于状态栈来模拟递归流程：

void fIterative(int x0)
{
    std::stack<StackFrame> myStack;
    myStack.emplace(x0, -1); // 初始状态：x0，未进入循环

    while (!myStack.empty())
    {
        auto frame = myStack.top();
        myStack.pop();

        int x = frame.x;
        int u = 2 * x + 1;

        if (frame.i == -1)
        {
            // 刚进入函数，执行开头的输出和判断
            cout << u - 10 << ": ";
            if (u > n)
                continue;

            // 先把当前状态压回栈，标记要开始第0次循环
            myStack.emplace(x, 0);
            // 执行第0次循环的前半部分：输出u-i，然后压入递归调用的状态
            cout << u << "-" << 0 << "  ";
            myStack.emplace(u, -1);
        }
        else
        {
            // 从递归返回，执行break输出
            cout << "break" << endl;

            int current_i = frame.i;
            // 判断是否还有下一次循环
            if (current_i + 1 < iMax)
            {
                // 压回当前状态，标记下一次循环的i
                myStack.emplace(x, current_i + 1);
                // 执行下一次循环的前半部分
                cout << u << "-" << (current_i + 1) << "  ";
                myStack.emplace(u, -1);
            }
            // 循环结束，无需再处理
        }
    }
}

逻辑解释 #

• 当i=-1时：对应递归函数刚被调用的阶段，执行函数开头的u计算、输出，判断终止条件。如果未终止，先把当前函数的状态（x，i=0）压回栈，再压入递归调用的状态（u，i=-1）——这样栈会先处理递归调用，等递归返回后再回到当前函数的循环步骤。
• 当i>=0时：对应递归调用完成后，执行break输出，然后判断是否还有下一次循环。如果有，就压回当前状态（x，i+1），再压入下一次递归调用的状态，继续模拟递归流程。

测试验证 #

修改后运行代码，迭代版本的输出会和递归版本完全一致，完美还原递归的执行顺序，包括递归调用后的break输出。

内容的提问来源于stack exchange，提问作者RocketSearcher