University of Alberta Dictionary of Cognitive Science: Divide and Conquer

Divide and conquer is an approach to solving a problem that is a special case of means-ends analysis. In divide and conquer, one solves a problem by first defining a subgoal that involves solving a smaller version of the same kind of problem. In other words, divide and conquer is the explicit use of recursion to solve a problem.

For example, consider the Towers of Hanoi problem, in which a stack of different sized discs are moved from one location to another (using a third “spare” location as well) under the restrictions that only one disc is moved at a time, and a larger disc can never be placed on a smaller one. A solution to the Towers of Hanoi problem points to the recursive nature of divide and conquer. We solve the bigger problem by first solving a smaller version of the same kind of problem. To move a stack of n discs to location C, we first move the smaller stack of n-1 discs to location B. “Moving the stack” is the same kind of procedure for the n discs and for the n-1 discs. The whole approach is recursive in the sense that to move the big stack, the same procedure must first be used to move the smaller stack on top of the largest disc.

The recursive nature of the solution to the Towers of Hanoi is made obvious if we write a pseudocode algorithm for moving the disks. Let us call our procedure MoveStack(). It will take four arguments: the number of discs in the stack to be moved, the starting location, the “spare” location, and the goal location. So, if we had a stack of three discs at location A, and wanted to move the stack to location C using location B as the “spare”, we would execute MoveStack (3, A, B, C).

The complete definition of the procedure is as follows:

MoveStack (N, Start, Spare, Goal)

If N = 0 Exit

Else MoveStack (N-1, Start, Goal, Spare)

Move remaining disk from Start to Goal

MoveStack (N-1, Spare, Start, Goal)

End If

Note the explicit recursion in this procedure, because MoveStack () calls itself to move a smaller stack of disks stacked on top of the disk that it is going to move. That is, when we execute MoveStack (3, A, B, C), it will work by recursively executing MoveStack (2, A, C, B), which in turn will recursively execute MoveStack (1, A, B, C).

References:

Knuth, D. E. (1997). The Art of Computer Programming. Volume 3: Sorting and Searching (3rd ed.). Reading, Mass.: Addison-Wesley.

(Added September 2010)