如何将递归函数转换为迭代函数

Question

我正在尝试使用堆栈将此递归函数转换为迭代函数：

void GetToTownRecursive(int x, Country &country, AList *accessiblesGroup, vector<eTownColor> &cities_colors)
{

    cities_colors[x - 1] = eTownColor::BLACK;
    accessiblesGroup->Insert(x);

    List *connected_cities = country.GetConnectedCities(x);
    if (!connected_cities->IsEmpty())
    {
        ListNode *curr_city = connected_cities->First();
        while (curr_city != nullptr)
        {
    
            if (cities_colors[curr_city->GetTown() - 1] == eTownColor::WHITE)
            {
                GetToTownRecursive(curr_city->GetTown(), country, accessiblesGroup, cities_colors);
            }
            curr_city = curr_city->GetNextNode();
        }
    }
}

该函数将城镇编号作为输入，并返回与该城镇连接（直接和间接）的城镇列表。

由于递归调用后采取的唯一操作是提升列表迭代器 - curr_city，因此我在转换它时遇到了困难。在这种情况下我应该将什么推入堆栈？

很高兴得到您的帮助！

Answer 1

递归呼叫后采取的动作是整个While循环的剩余时间（所有剩余的迭代）。在堆栈上，您必须节省任何在递归电话期间可能会更改的变量，但需要之后需要。在这种情况下，这仅仅是curr_city的值。

如果goto仍然是一件事情，则可以用以下方式替换递归调用：

1. save curr_city
2. set x = curr_city-＆gt; gettown（）
3. goto 从结束开始

，您必须

4. 检查堆栈
5. ，如果保存curr_city，将其还原并在（3）之后恢复并goto，

因为它是不可接受的可接受此类gotos事物（它们使您的代码难以理解），您必须将功能分解为3个顶级部分：

• 第1部分：第一个递归电话之前的所有内容，以1-3
• 第2部分：一个循环 结束递归呼叫之间的所有内容，如果到另一个递归电话，则以1-3结尾，如果没有进行4-5。
• 第3部分：上次递归呼叫之后发生的任何事情，在这种情况下，这是什么都没有的。

通常，在重新排列后，您可以进行大量的清理和简化。

Answer 2

基本想法将是以下内容。

void GetToTown(int x, Country &country, AList *accessiblesGroup,
   vector<eTownColor> &cities_colors)
{
    Stack<int> pendingX = new ...
      
    pendingX.push(x);
    
    while (!pendingX.isEmpty()) {
        int localX = pendingX.Pop();
        cities_colors[localX - 1] = eTownColor::BLACK;
        accessiblesGroup->Insert(localX);
        
        List *connected_cities = country.GetConnectedCities(localX);
        if (!connected_cities->IsEmpty())
        {
            ListNode *curr_city = connected_cities->First();
            while (curr_city != nullptr)
            {            
                if (cities_colors[curr_city->GetTown() - 1] == nColor::WHITE)
                {
                    pendingX.Push(curr_city->GetTown());
                }
                curr_city = curr_city->GetNextNode();
            }
         }
    }
}