CODEWITHSUNDEEP
pythonalgorithmcomputer-science
TimelordViktorious
TimelordViktorious

Reputation: 336

Iterative Divide and Conquer algorithms

I am trying to create an algorithm using the divide-and-conquer approach but using an iterative algorithm (that is, no recursion).

I am confused as to how to approach the loops.

I need to break up my problems into smaller sub problems, until I hit a base case. I assume this is still true, but then I am not sure how I can (without recursion) use the smaller subproblems to solve the much bigger problem.

For example, I am trying to come up with an algorithm that will find the closest pair of points (in one-dimensional space - though I intend to generalize this on my own to higher dimensions). If I had a function closest_pair(L) where L is a list of integer co-ordinates in ℝ, how could I come up with a divide and conquer ITERATIVE algorithm that can solve this problem?

(Without loss of generality I am using Python)

Upvotes: 1

Views: 3853

Answers (1)

Andrew
Andrew

Reputation: 518

The cheap way to turn any recursive algorithm into an iterative algorithm is to take the recursive function, put it in a loop, and use your own stack. This eliminates the function call overhead and from saving any unneeded data on the stack. However, this is not usually the "best" approach ("best" depends on the problem and context.)

They way you've worded your problem, it sounds like the idea is to break the list into sublists, find the closest pair in each, and then take the closest pair out of those two results. To do this iteratively, I think a better way to approach this than the generic way mentioned above is to start the other way around: look at lists of size 3 (there are three pairs to look at) and work your way up from there. Note that lists of size 2 are trivial.

Lastly, if your coordinates are integers, they are in Z (a much smaller subset of R).

Upvotes: 4

Related Questions