The big idea: A recursive trace has two halves. Going down, each call is made and waits. Going up, each returns a value to the call that made it.
Most lost marks come from tracing only the first half and guessing the second.
The layout that works: Write each call indented one level further than the one that made it. Leave the return value blank on the way down, and fill it in on the way back up.
The indentation is not decoration — it is what stops you losing which call you are in.
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
def sumTo(n):
if n == 0:
return 0
return n + sumTo(n - 1)
sumTo(3)static int sumTo(int n) {
if (n == 0) {
return 0;
}
return n + sumTo(n - 1);
}
sumTo(3);sumTo(3) 3 + sumTo(2) → waits
sumTo(2) 2 + sumTo(1) → waits
sumTo(1) 1 + sumTo(0) → waits
sumTo(0) base case → returns 0
sumTo(1) 1 + 0 → returns 1
sumTo(2) 2 + 1 → returns 3
sumTo(3) 3 + 3 → returns 6Nothing is added on the way down: Going down, no arithmetic happens at all — each call simply waits, holding its n.
Every addition takes place on the way up, once the base case has finally returned something to add to. Answers that add as they descend get the right answer here by luck, and the wrong one as soon as the operation is subtraction or division.
Know your predicted grade
Take timed mock exams and get detailed feedback on every answer. See exactly where you're losing marks.
Three questions before you write any code
Base case
Which input is so small you already know the answer? An empty word holds no letter a, so the answer is 0.
Smaller step
How does each call make the problem one step smaller? Drop the first letter and call again on the rest.
Combine
What is done with the returned value on the way up? Add 1 if the dropped letter was an a, otherwise pass the value straight back.
def countA(word):
if word == "":
return 0
if word[0] == "a":
return 1 + countA(word[1:])
return countA(word[1:])
countA("papa")static int countA(String word) {
if (word.equals("")) {
return 0;
}
if (word.charAt(0) == 'a') {
return 1 + countA(word.substring(1));
}
return countA(word.substring(1));
}
countA("papa");countA("papa") countA("apa") → waits
countA("apa") 1 + countA("pa") → waits
countA("pa") countA("a") → waits
countA("a") 1 + countA("") → waits
countA("") base case → returns 0
countA("a") 1 + 0 → returns 1
countA("pa") 1 → returns 1
countA("apa") 1 + 1 → returns 2
countA("papa") 2 → returns 2One recursive call per step: Every function you construct or trace in this course makes one recursive call each time it runs, like sumTo and countA. The calls form a single line: down to the base case, then back up.
How this is tested — you must show the calls descending and the values returning, in a readable layout. It comes up two ways:
Paper 2 — working with code
- Trace a recursive function and give the output, 3-5 marks
- State the value returned by a given call
- Count how many calls are made
Paper 2 — constructing code
- Construct a recursive function for a described task, e.g. the sum of a number's digits
- Identify why a call never reaches its base case
The classic trap: Tracing only downwards and then guessing. The returns are where the arithmetic happens — and with subtraction or division, adding on the way down gives a different and wrong answer.
Trace mystery(4), where mystery(n) returns 1 if n <= 1, and otherwise returns n * mystery(n - 2). State the value returned and how many calls are made.
Model answer plan
See the answer broken into clear points, with guidance on how each point earns marks.