1.5 DIVIDE AND CONQUER ALGORITHMS 25for i = 1 to numberSmaller do
DivideAndConquer(smallerSets[i], smallerSizes[i], smallSolution[i])
end for
CombineSolutions(smallSolution, numberSmaller, solution)
end if
This algorithm will first check to see if the problem size is small enough to
determine a solution by some simple nonrecursive algorithm (called Direct-
Solution above) and, if so, will do that. If the problem is too large, it will
first call the routine DivideInput, which will partition the input in some
fashion into a number (numberSmaller) of smaller sets of input values.
These smaller sets may be all of the same size or they may have radically differ-
ent sizes. The elements in the original input set will all be put into at least one
of the smaller sets, but values can be put in more than one. Each of these
smaller sets will have fewer elements than the original input set. The Divide-
AndConquer algorithm is then called recursively for each of these smaller
input sets, and the results from those calls are put together by the Combine-
Solutions function.
The factorial of a number can easily be calculated by a loop, but for the pur-
pose of this example, we consider a recursive version. You can see that the fac-
torial of the number N is just the number N times the factorial of the number
N 1. This leads to the following algorithm:
Factorial( N )
N is the number we want the factorial for
Factorial returns an integerIf (N = 1) then
return 1
else
smaller = N - 1
answer = Factorial( smaller )
return (N * answer)
end if
This algorithm is written in simple detailed steps so that we can match
things up with the standard algorithm above. Even though earlier in this chap-
ter we discussed how multiplications are more complex than additions and are,
therefore, counted separately, to simplify this example we are going to count
them together.