How to convert this recursive problem to iterative? Line Simplification algorithm fails to run due to Maximum Recursion Depth being hit

Question

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.

Answer 1

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.

Answer 2

Converting a recursive algorithm to be iterative usually involves doing the same thing that the compiler or interpreter does behind the scenes yourself, i.e. on front of the scenes. That can mean you have to program a call stack and keep track of the variable values in recursive calls yourself, so that they live in a user-defined data structure rather than on the system-provided call stack. It's more effort and usually less readable than using proper recursion, but it can allow you to circumvent system limitations - rather than hitting the built-in recursion limit you only hit the built-in limit on the size of dynamically allocated data.

Of course, it's also often possible to solve the same problem iteratively in a completely different way, sometimes even better. But then it's not so much converting the recursion as replacing it with something completely different. It depends on the problem whether that is possible or not.

Answer 3

I would use a stack, but just keep it as simple as possible. After all, all you need to know what to do next is a pair of numbers.

def line_simple(array, epsilon):
    keep = [False for i in array]
    keep[0], keep[-1] = True, True
    stack = deque()
    stack.append((0, len(array) -1))

    while len(stack) != 0:
        left, right = stack.pop();
        worst_distance, worst_index = find_worst(array, left, right)

        if worst_distance > epsilon:
            keep[worst_index] = True
            stack.append((left, worst_index))
            stack.append((worst_index, right))

    return keep

All you have to do is write find_worst. Note that find_worst should take arguments as I've shown; you should not do find_worst(array[left:right]) which makes a copy of the array. Make sure that find_worst returns 0 if right-left = 0 or 1.