Data Structures Examples
Many data structures are collections which can be divided
into subcollections that can be independently processed.
For example, to add the numbers stored in array X between positions
FIRST and LAST. We can choose the two simplest cases as base cases:
- FIRST=LAST:
- Answer: X[FIRST].
- FIRST+1=LAST:
- Answer: X[FIRST] + X[LAST].
Otherwise:
- P1: add up the numbers in X between positions FIRST and M; the
answer is S1.
- P2: add up the numbers in X between positions M+1 and LAST; the
answer is S2.
- Combine: S = S1 + S2.
The exact way we divide up the array does not affect the
correctness of this strategy: M can be any value at all,
FIRST<M<LAST.
Remark: Only one the first base case is really necessary.