I'm trying to convert this recursive function to an iterative one using a stack:

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

The function takes a town number as an input and returns a list of towns that are connected to that town (directly as well as indirectly).

I'm having difficulty converting it because of the while loop within and because the only action taken after the recursive call is the promotion of the list iterator - curr_city. What should I push into the stack in this case?

Would be glad for your help!

CodePudding user response：

The action taken after the recursive call is the whole remainder of the while loop (all the remaining iterations). On the stack, you have to save any variables that could change during the recursive call, but will be needed after. In this case, that's just the value of curr_city.

If goto was still a thing, you could then replace the recursive call with:

1. save curr_city
2. set x = curr_city->GetTown()
3. goto start

Then at the end, you have to

4. check stack
5. If there's a saved curr_city, restore it and goto just after (3)

Because it's not acceptable to use gotos for this sort of thing (they make your code hard to understand), you have to break up your function into 3 top-level parts:

• part 1: all the stuff before the first recursive call, ending with 1-3
• part 2: a loop that does all the stuff between recursive calls, ending with 1-3 if it gets to another recursive call, or 4-5 if it doesn't.
• part 3: anything that happens after the last recursive call, which is nothing in this case.

Typically there is then a lot of cleanup and simplification you can do after this rearrangement.

CodePudding user response：

The basic idea would be something like the following.

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