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.
Nothing 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.
What changes when a function calls itself twice
- The calls form a tree, not a line
- The left branch is fully evaluated before the right one begins
- The same value is computed repeatedly — fib(2) is calculated three times in fib(5)
- Calls grow exponentially: fib(30) makes over 1.3 million calls
- Which is why naive Fibonacci is the standard example of recursion done badly
Count the calls, not just the answer: A common question asks how many times a function is called, not what it returns. Draw the tree and count the nodes.
And say which values repeat — that is the observation the question is usually reaching for.
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 — the algorithmic-thinking question
- Draw the call tree for a branching recursion
- Explain why a value is computed repeatedly
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 mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.