Divide and conquer algorithm: Encyclopedia II - Divide and conquer algorithm - Disadvantages

Divide and conquer algorithm - Disadvantages

One commonly argued disadvantage of a divide-and-conquer approach is that recursion is slow: the overhead of the repeated subroutine calls, along with that of storing the call stack (the state at each point in the recursion), can outweigh any advantages of the approach. This, however, depends upon the implementation style: with large enough recursive base cases, the overhead of recursion can become negligible for many problems.

Another problem of a divide-and-conquer approach is that, for simple problems, it may be more complicated than an iterative approach, especially if large base cases are to be implemented for performance reasons. For example, to add N numbers, a simple loop to add them up in sequence is much easier to code than a divide-and-conquer approach that breaks the set of numbers into two halves, adds them recursively, and then adds the sums. (On the other hand, the latter approach turns out to be much more accurate in finite-precision floating-point arithmetic.)

Alternatively, an algorithm can be designed by a divide-and-conquer approach and then implemented in an iterative style; of course, any recursive algorithm can be simulated in an iterative style, but by reordering the computation it is sometimes possible to avoid simulating a recursive call stack altogether. The Cooley-Tukey FFT algorithm is a prime example of this: it was initially derived in a divide-and-conquer style, but implementations were traditionally implemented iteratively in a re-ordered fashion that avoided call-stack-like storage (although some recent implementations have returned to a recursive style).

Adapted from the Wikipedia article "Disadvantages", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki