19 Advanced algorithms and recursion
Design and compare searches and sorts, trace recursive routines and explain termination and call-stack use.
Section Paper 3 · Advanced Theory · Sections 13–20
Mapped to Cambridge International AS & A Level Computer Science 9618, 2027–2029 Version 2. These original lessons and self-checks are independent study support; they are not Cambridge papers, official marks or grades. The course does not yet provide a timed four-paper simulation or a locked-down Paper 4 programming environment.
Before you begin
- Use the 2027–2029 syllabus for your exam year. AS candidates study Sections 1–12; A Level candidates study Sections 1–20. Paper 4 uses a programming language chosen from Python, Java or Visual Basic in console mode.
Work on paper. Try each question before revealing help, and explain why your method works.
Quick readiness check
What does a recursive base case do?
What you will learn
- Explain the key representations, structures or processes in this syllabus section
- Apply the method to a new computer-science example
- Justify a design choice and check its limits
Search and sort methods depend on data and input order
Linear search checks items in sequence and works on unsorted data. Binary search repeatedly halves a sorted search range; it is efficient for random access but requires sorted data and careful boundary updates.
Bubble sort swaps adjacent out-of-order items; insertion sort inserts each new item into the already sorted prefix. Their performance depends on input size and initial order; describe the case and assumptions when comparing them.
Recursion solves a smaller version of the same problem
A recursive routine calls itself with a smaller or simpler input. A base case stops recursion; each recursive step must make progress toward that case.
Each call stores local state and a return address on the call stack. When the base case returns, suspended calls unwind in reverse order. Missing or unreachable base cases can cause unbounded calls and stack exhaustion.
Pause and explain
What happens to local variables when a recursive call returns?
Worked example
A sorted list contains 16 items. How many times can binary search halve the range before at most one item remains?
Show the worked solution
- After one halving there are 8 items.
- Then 4, then 2, then 1.
- Four halvings reduce 16 to 1.
Answer Four halvings, so the number of steps grows logarithmically with list size.
Try a topic test
Choose Easy, Normal or Difficult. Save your answers and open worked review after finishing.
Test this topic →From guided practice to a new situation
Write your answer and reasoning first. Use a hint only if you are stuck. The model solution is for self-checking; your written work is not automatically marked.
Use linear search on [8, 3, 6, 11] to find 6. Show the comparisons and stopping point.
Give me a hint
Check from the first item and stop once the target is found.
Compare my reasoning
- Compare 6 with 8: not equal.
- Compare 6 with 3: not equal.
- Compare 6 with 6: found at position 3.
Three comparisons; the target is at position 3 (using one-based positions).
Look for these in your work
- Order preserved
- Comparisons correct
- Position stated
Trace recursive Sum(n), where Sum(0)=0 and Sum(n)=n+Sum(n−1). Find Sum(4).
Give me a hint
Expand until the base case, then unwind.
Compare my reasoning
- Sum(4)=4+Sum(3).
- Continue: 4+3+2+1+Sum(0).
- Sum(0)=0, so add the terms.
10.
Look for these in your work
- Base case reached
- Terms correct
- Unwinding result correct
A recursive factorial function calls Factorial(n−1) until n=1. Explain the base case, progress measure and one failure if the test is missing.
Give me a hint
State the stopping input and why each call approaches it.
Compare my reasoning
- The base case returns 1 when n=1.
- For positive n, n decreases by one per call, moving toward 1.
- Without the test, calls continue below zero until the call stack is exhausted.
Base case n=1; n decreases toward 1; missing the base case can cause unbounded calls and stack exhaustion.
Look for these in your work
- Stop condition
- Progress measure
- Failure explained
Common mistakes
- Applying binary search to unsorted data.
- Using the wrong loop bound and skipping a candidate item.
- Writing recursion without a base case or without decreasing the problem.
What can you explain now?
What condition does binary search require?
Compare with the explanation
The data must be ordered by the search key.
Halving is valid only when comparison tells which half can be discarded.
After trying it yourself, choose your next review. This is your self-assessment.
Your review choice appears on Today. Sign in to sync it across devices.
Make it stick
When is binary search valid, how do sorting methods behave, and what makes recursion terminate?
If you needed the solution, close it and solve the problem again from a blank page. A correct answer is stronger when you can explain the reason for each step.