Community resourceWorksheet

OCR H446 2.2.2 Divide and conquer

Part 3 of 14 · H446 2.2.2 · Computational methods

Divide and conquer appears in H446 2.2.2 as a method with three named stages, and students can usually list them without being able to trace one. Starting from summing a list, this worksheet builds the divide, solve and combine shape, then asks for a working recursive implementation and a judgement about when a loop would serve better.

Students will:

  • identify the divide, solve and combine stages in a described method
  • trace recursive calls as a tree and write each returned subtotal back upwards
  • explain why a call waits rather than disappearing while its children run
  • implement a recursive method that preserves the original list, handles an empty list and always uses a smaller slice
  • weigh a recursive design against a loop for very large inputs on a single processor

Inside: 7 explanation cells, 1 multiple-choice question, 2 fill-in-the-blanks cells, 1 written answer and 2 Python tasks. 20 marks, about 25 to 35 minutes.

Series: H446 2.2.2 · Computational methods, part 3 of 14.

Shared by Coding PathwayVerified teacher

  • 13 cells
  • About 30 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 3 Sept 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Divide and conquer

A media archive must process a large list of clip durations. Divide and conquer solves smaller instances of the same problem and combines their results.

By the end, you will be able to

  • identify divide, solve and combine stages;
  • distinguish divide and conquer from general decomposition;
  • trace a recursive divide-and-conquer function;
  • evaluate when splitting helps and when overhead dominates.

Reactivate: recursion needs a base case and progress towards it.

The repeated shape

Divide, solve and combine[9, 3, 7, 1, 8, 2, 6, 4]divide and solve leftdivide and solve rightcombine sorted resultsThe subproblem has the same form; the combine rule turns partial solutions into the whole solution.

A divide-and-conquer solution follows three ideas:

  1. Divide one problem into smaller instances of the same form.
  2. Conquer each smaller instance, often recursively. Independent subproblems may be carried out simultaneously when suitable processing resources are available.
  3. Combine partial answers into the answer for the original problem.

General decomposition can produce different components such as input, validation and output. Divide and conquer specifically produces smaller versions of the same task and needs a combining rule. Simultaneous work can reduce elapsed time, but coordination and combination still have a cost.

Worked model: sum a list

For [8, 3, 5, 2], split into [8, 3] and [5, 2]. Split again until each list has one value. Those base answers are 8, 3, 5 and 2. Combine neighbouring answers: 8 + 3 = 11; 5 + 2 = 7; then 11 + 7 = 18.

The method is correct because every value appears in exactly one subproblem and addition combines the partial totals. For a simple sum, however, recursive slicing may cost more than one loop. A method can illustrate the pattern without being the best implementation for every task.

Multiple choice1 mark

Which feature is essential to divide and conquer?

  • AEvery subproblem uses a different algorithm
  • BAll work must run on separate processors
  • CPartial solutions are combined to solve the original problem
  • DThe input is always divided into exactly two parts
Fill in the blanks3 marks
Divide and conquer creates smaller instances of the gap 1 problem, stops at a gap 2, and gap 3 the partial answers.
  • same
  • base case
  • combines
  • unrelated

Guided trace

For [6, 1, 4], write the calls as a tree. Mark the one-item base calls, then write each returned subtotal upwards. A call does not disappear when its children run: it waits so their results can be combined.

Worked example
def sum_divide(values):
    if len(values) <= 1:
        return 0 if len(values) == 0 else values[0]
    middle = len(values) // 2
    left_total = sum_divide(values[:middle])
    right_total = sum_divide(values[middle:])
    return left_total + right_total

print(sum_divide([6, 1, 4]))

Independent implementation

Complete the same method. Preserve the original list, handle an empty list, and make every recursive call use a smaller slice.

Coding task7 marks
def sum_divide(values):
    # Base case, divide, recursively solve, then combine.
    pass
Written answer5 marks

A developer proposes this recursive method for millions of values on one processor. Explain one benefit of the design and two factors that should be considered before choosing it over a loop.

Consider independent subproblems, recursion/slicing overhead and the combine operation.

Students type their answer here.

Closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks4 marks
Divide and conquer creates checkpoint gap 1 instances of one problem form. These may be solved checkpoint gap 2 or, when independent resources permit, simultaneously. A combine rule turns checkpoint gap 3 solutions into the whole answer. The original problem form is checkpoint gap 4 at each level.

Review your understanding

Before submitting, check that you can explain the central distinction in your own words, expose the intermediate state that supports your answer and apply the method in an unfamiliar context.