Recursion to iteration preserving variables and order of calls

Question

I have a very complex code to transform from recursion to iteration. I don't know how to do that with this kind of code :

read(std::queue<int>& rules, std::queue<double>& data)
{
  int r = rules.top();
  rules.pop();
  switch(r)
  {
    case 1:
    {
      double a = data.front(); data.pop();
      read(rules, data);
      double b = data.front(); data.pop();
      read(rules, data);
      double c = a + b;
      data.push(c);
    }
    break;
    case 2:
    {
      read(rules, data);
      data.pop();
    }
    break;
    case 3:
    {
      data.push(0.0);
    }
  }
}

I have no idea how to start in this kind of situation...

http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration may help — Matthew Fisher, Aug 23 '16 at 14:21

Franck · Accepted Answer · 2016-08-23T16:18:26.757

The standard way is to simulate your recursion stack with an explicit stack as a local variable.

struct Task {
  int caseValue; /* 1, 2, 3 */
  std::queue<int>& rules;
  std::queue<double>& data;
  void execute(std::stack<Task>& agenda)
     { // do one thing and put next tasks in the agenda
       // by using agenda.push_back
     }
};
typedef std::stack<Task> Agenda;
void read(...) {
  Agenda agenda;
  int r = rules.top();
  rules.pop();
  agenda.push_back(Task(r, rules, data));
  while (!agenda.empty()) {
    Task task = agenda.top();
    agenda.pop_back();
    task.execute(agenda);
  };
}

Here the agenda simulates your recursion stack. The iterative version may be less efficient, but it may ease the debugging since you can set a breakpoint within the while loop.

Recursion to iteration preserving variables and order of calls

1 Answers1