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

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();
        }
    }
}

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

我在转换它时遇到困难，因为其中有 while 循环，而且递归调用后唯一采取的操作是提升列表迭代器 - curr_city。在这种情况下，我应该将什么压入堆栈？

很高兴得到您的帮助！

Answer 1

递归调用后执行的操作是 while 循环的全部剩余部分（所有剩余迭代）。在堆栈上，您必须保存在递归调用期间可能更改但之后需要的所有变量。在这种情况下，这只是 curr_city.

的值

如果 goto 仍然有效，您可以将递归调用替换为：

保存curr_city
设置x = curr_city->GetTown()
转到开始

那么在最后，你必须

检查堆栈
如果有已保存的 curr_city，请将其恢复并转到 (3)

因为不可以接受使用 gotos 来做这种事情（它们使您的代码难以理解），所以您必须将您的函数分解为 3 top-level 零件：

第 1 部分：第一次递归调用之前的所有内容，以 1-3
第 2 部分：在递归调用之间执行所有操作的循环，如果到达另一个递归调用则以 1-3 结束，否则以 4-5 结束。
第 3 部分：在 last 递归调用之后发生的任何事情，在这种情况下什么都不是。

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

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();
            }
         }
    }
}

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

How to transform a recursive function to an iterative one

c++

algorithm

recursion

loops

data-structures