将递归改为迭代函数

Question

我有一个用于导出信息的递归函数，出于效率原因，我想将其转换为迭代函数（下面的玩具问题）。但是，由于调用递归函数后递归函数中有语句，因此我没有获得有效的迭代解决方案。

#include <iostream>
#include <stack>
using namespace std;

int n = 100;
int iMax = 2;

void fRecursive(int x)
{
    int u = 2 * x + 1;
    cout << u - 10 << ": ";

    if (u > n)
        return;

    for (int i = 0; i < iMax; ++i)
    {
        cout << u << "-" << i << "  "; 
        fRecursive(u);
        cout << "break" << endl;
    }
}

void fIterative(int x0)
{
    std::stack<int> myStack;
    myStack.push(x0);

    while (!myStack.empty())
    {
        int curx = myStack.top();
        myStack.pop();

        int u = 2 * curx + 1;
        cout << u - 10 << ": ";
        if (u > n)
            continue;

        for (int i = 0; i < iMax; ++i)
        {
            myStack.push(u);
            cout << u << "-" << i << "  ";

            cout << "break\n";
        }
    }
}

int main()
{
    int x0 = 10;

    cout << "Start Recursion" << endl;
    fRecursive(x0);
    cout << "End Recursion" << endl << endl;
    
    cout << "Start Iterative" << endl;
    fIterative(x0);
    cout << "End Iterative" << endl << endl;
    
    return 0;
}

当调用递归函数后没有代码块时，我设法将递归更改为迭代函数，但当该函数存在时，我没有设法这样做。

Answer 1

作为通用解决方案，您可以模仿将 state 推入堆栈。您需要的相关上下文还包括

i

的值，因此您可以堆叠 x 和

i

的

pairs

。在一些实际场景中（比如这个玩具示例），您可能会找到在堆栈上没有附加元素的情况下完成此操作的方法，但我相信对于更通用的方法，您会希望拥有该

i

（或您迭代的任何内容）也叠起来了。

以下是您的示例的外观：

void fIterative(int x)
{
    std::stack<std::pair<int, int>> myStack;

    while (true)
    {
        int u = 2 * x + 1, i = 0;
        std::cout << u - 10 << ": ";
        myStack.push(std::make_pair(u, 0));
        
        while (true) {
            std::pair<int, int> p = myStack.top();
            myStack.pop();
            x = p.first;
            i = p.second;
            if (i < iMax && x <= n) {
                break;
            }
            if (myStack.empty()) {
                return;
            }
            std::cout << "break" << std::endl;
        }
        
        std::cout << x << "-" << i << "  "; 
        myStack.push(std::make_pair(x, i+1));
    }
}