How to Convert Recursive Problem to Iterative for Line Simplification Algorithm

algorithmspythonrecursion

I am implementing the Douglas, Peucker's Line Simplification algorithm in Python. I started with this implementation. However, it fails to run in Python due to Maximum Recursion Depth being hit. How can I convert this algorithm to a iterative one? I am not able to imagine this problem in an iterative view.

My expectation is to get approach/hint which can be used rather than actual code. Is it possible to use some internal stack to resolve the stack overflow (or avoid the maximum recursion depth)?

Update:
Found the iterative implementation of the algorithm here.

Best Answer

I would simulate in the most generic way as follows: This is what I believe the low-level machine would do.

func(Param x) {

  Stack stack = new Stack();
  Frame frame = new Frame(x);
  push(frame);

  while (!stack.empty()) {
    frame = stack.pop();

    if (baseCase) {
       createResult(frame);
    } else {
       newFrame = doWork(frame);
       stack.push(frame);
       stack.push(newFrame);
    }
  }

  return frame.getResult();
}

You can define Frame as follows:

class Frame {
   FrameData state;
   Data sharedData;
   Param inputParam;

   Result getResult() {
     ..compute result from 'state' and 'sharedData'
   }
}

Now you can wonder why there is only one push into the stack even though you have 2 recursive calls. It is because The first recursive call is pushed into the stack with a frame having different state and sharedData compared to the frame pushed into the stack by the second call.

Since you said, you only want approach and hint. I hope this is enough. The details is done in the method doWork(). There Frame's instances variables are changed.

I took me a while to come up with this. Hopefully, there is nothing wrong here.

Related Topic