Go backward to 3.12 Generic Algorithm Specialized by Strategy
Go up to 3 An Example of Concept Webs: Programming Concepts
Go forward to 3.14 Generic Divide-and-Conquer Sequence Algorithm
3.13 Generic Divide-and-Conquer Algorithm
A generic divide-and-conquer algorithm is a generic
algorithm whose steps are structured
according to the following strategy:
This concept is one of many known ways of narrowing the generic
algorithm concept in terms of a strategy, which
gives a specific structure to the steps of the algorithm.
- Construct the output directly and return it, if the input is
simple enough. Otherwise:
- Divide the input into two or more (a finite number)
of smaller inputs.
- Recursively apply the algorithm to each of the smaller inputs
produced in the first step.
- Combine the outputs from the recursive applications to produce
the output corresponding to the original input.