Mission 1 · Spec 2.2.1
Programming techniques
Recursion versus iteration, global and local variables, modularity, and passing parameters by value and by reference.
- Starter 5 min
- Learn 15 min
- Lab 25 min
- Quiz 10 min
- Exam 15 min
Russian dolls
To count the dolls in a set of Russian dolls, you open one and count the dolls inside it, which means opening the next one... When do you stop?
Reveal
When you reach the smallest doll, which doesn't open. That's the base case. A recursive subroutine calls itself on a smaller version of the problem until it reaches the base case.
Key ideas
Recursion
A subroutine that calls itself. Needs a base case (stopping condition) and must move towards it. Each call adds a frame to the call stack.
✓ Elegant, natural for trees and divide-and-conquer
✗ Uses more memory; stack overflow if too deep; can be slower
Iteration
Repeating code with a loop. Usually uses less memory and is faster, but some problems (tree traversal, backtracking) are harder to express.
Global vs local
Local variables exist only inside their subroutine: less memory, no accidental side effects, subroutines are self-contained. Globals are accessible everywhere, but make code harder to test and maintain.
Modularity
Splitting a program into subroutines (functions and procedures) with clear interfaces. Easier to test, reuse, maintain and divide between a team.
By value vs by reference
By value: a copy of the data is passed; the original can't be changed. By reference: the address of the data is passed; changes affect the original. OCR pseudocode: procedure f(x:byVal) / (x:byRef).
Recursion and the call stack
By value vs by reference
Exam-style questions
1. Rewrite this recursive function iteratively.
[4 marks]function total(n) if n == 0 then return 0 else return n + total(n - 1) endifendfunction
Mark scheme
- Function header with parameter n (1)
- Running total initialised to 0 (1)
- Loop from 1 to n (or n down to 1) adding each value (1)
- Returns the total (1)
2. Discuss the advantages and disadvantages of recursion compared with iteration.
[6 marks]Mark scheme (levels)
- Level 3 (5–6): well-developed, balanced discussion.
- Indicative content: recursion can be more natural and concise for problems defined recursively (trees, divide and conquer); each call uses stack memory; risk of stack overflow; function call overhead makes it slower; iteration is more memory-efficient; some algorithms (e.g. tree traversal) are harder to write iteratively.
TUTOR NOTES
- Lab prompt: compare the number of calls for fib(6) and factorial(6). Why is naive Fibonacci so wasteful?
- Misconception: passing an array by value never copies it. Discuss what the spec expects in exam answers.
Mission 2 · Spec 2.2.1
Object-oriented techniques and IDEs
Classes, objects, methods, attributes, constructors, inheritance, encapsulation and polymorphism in OCR pseudocode, plus IDE features for debugging.
- Starter 5 min
- Learn 15 min
- Lab 15 min
- Quiz 10 min
- Exam 15 min
Cookie cutter
A cookie cutter can make hundreds of cookies, each with its own icing. Which is the class and which are the objects?
Reveal
The cutter is the class (the template). Each cookie is an object (an instance) with its own attribute values, like icing colour.
OOP in OCR pseudocode
class Pet private name public procedure new(givenName) name = givenName endprocedure public function getName() return name endfunction public function speak() return "..." endfunctionendclassclass Dog inherits Pet public procedure new(givenName) super.new(givenName) endprocedure public function speak() return "Woof" endfunctionendclassrex = new Dog("Rex")print(rex.getName() + " says " + rex.speak())
Constructor
The new method runs when an object is created (instantiated), setting initial attribute values.
Encapsulation
name is private; other code uses the public getName() method.
Inheritance
Dog inherits Pet: Dog gets Pet's attributes and methods; super.new calls the parent's constructor.
Polymorphism
speak() is overridden in Dog, so the same call behaves differently depending on the object's class.
IDE features that help develop and debug: breakpoints, stepping through code, watch windows showing variable values, syntax highlighting, error diagnostics, auto-complete.
Spot the OOP feature
In the code above, which concept does each line show?Exam-style questions
1. Write a class Cat that inherits from Pet and overrides speak() to return "Meow".
Mark scheme
class Cat inherits Pet(1)- Constructor calling
super.new(givenName)(1) public function speak()(1)- returning "Meow", with endfunction / endclass (1)
2. Explain how encapsulation improves the reliability of a program.
[2 marks]Mark scheme
- Attributes can only be changed through the class's methods (1)
- which can validate changes / prevent accidental changes from elsewhere in the program (1)
TUTOR NOTES
- Practical: have the student implement Pet/Dog/Cat in their own language and call speak() on a list of mixed pets.
Mission 3 · Spec 2.2.2
Computational methods
Problem recognition, decomposition, divide and conquer, abstraction, backtracking, data mining, heuristics, performance modelling, pipelining and visualisation.
- Starter 5 min
- Learn 15 min
- Lab 15 min
- Quiz 10 min
- Exam 15 min
The maze
How do you get out of a maze you've never seen before?
Reveal
Try a path; when you hit a dead end, go back to the last junction and try a different way. That's backtracking. Always keeping your hand on the right-hand wall is a heuristic: a rule of thumb that usually works well enough.
The methods
Problem recognition
Identifying that a problem exists, what it is, and whether it can be solved computationally.
Divide and conquer
Repeatedly split a problem into smaller sub-problems until they are simple to solve, e.g. binary search, merge sort, quick sort.
Backtracking
Build a solution step by step; when a path fails, go back to the last decision point and try another option, e.g. maze solving, Sudoku.
Heuristics
Rules of thumb that give a good-enough solution quickly when an optimal one would take too long, e.g. A*'s estimate, the travelling salesman problem.
Data mining
Searching large data sets to find patterns and relationships, e.g. shopping habits, fraud detection. Raises privacy issues.
Performance modelling
Using mathematical models or simulations to predict how a system will behave under load before building or testing it for real.
Pipelining
Splitting a task into stages where the output of one feeds the next, so stages can work on different data at once.
Visualisation
Presenting data or processes as graphs, charts or diagrams so patterns are easier for people to understand.
Which method?
Exam-style questions
1. Explain why a delivery company might use heuristics to plan routes for its drivers.
[3 marks]Mark scheme
- Finding the optimal route through many drops is intractable / would take too long to compute (1)
- A heuristic finds a good-enough route quickly (1)
- Routes are needed every day / change often, so speed matters more than perfection (1)
2. Describe how backtracking could be used to find a path through a maze.
[3 marks]Mark scheme
- Follow a path, making a choice at each junction (1)
- When a dead end is reached, return to the most recent junction with untried options (1)
- Try a different option; repeat until the exit is found (1)
TUTOR NOTES
- Exam habit: these questions are almost always in context; describe how the method applies to the scenario.