The big idea: A recursive function solves a problem by calling itself on a smaller version of the same problem, until it reaches a case small enough to answer outright.
Two parts, always
- A base case that returns without recursing
- A recursive case that moves towards it
def factorial(n):
if n <= 1: # base case — stops the recursion
return 1
return n * factorial(n - 1) # recursive case — smaller n
# factorial(4) = 4 * factorial(3)
# = 4 * 3 * factorial(2)
# = 4 * 3 * 2 * factorial(1)
# = 4 * 3 * 2 * 1 = 24static int factorial(int n) {
if (n <= 1) { // base case — stops the recursion
return 1;
}
return n * factorial(n - 1); // recursive case — smaller n
}
// factorial(4) = 4 * factorial(3)
// = 4 * 3 * factorial(2)
// = 4 * 3 * 2 * factorial(1)
// = 4 * 3 * 2 * 1 = 24Both parts, or it never stops: No base case → it recurses forever until the call stack is exhausted: a stack overflow.
A recursive case that does not get closer → same result. factorial(n) calling factorial(n) never reaches 1.
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.
Each call gets a frame
A stack frame holds that call's own parameters, local variables and where to return to. factorial(4) puts four frames on the stack before any of them finishes.
Nothing returns until the base case
Every call is waiting on the one below it. The multiplications in factorial happen on the way back up, not on the way down.
Then they unwind
The base case returns 1, the call above multiplies and returns, and so on until the first call has its answer.
The stack is finite
Deep recursion uses real memory — one frame per call. A few thousand levels is often enough to exhaust it, which is why depth matters.
Why a stack, and not something else: Calls must return in exactly the reverse order they were made — the most recent first. That is last in, first out, so a stack is the only structure that fits.
This is the same call stack from B2.2, which is why the two topics connect.
Know your predicted grade
Take timed mock exams and get detailed feedback on every answer. See exactly where you're losing marks.
| Recursion | Iteration | |
|---|---|---|
| Suits | Self-similar structures — trees, nested data | Repeating a fixed number of times |
| Memory | One frame per level | Constant |
| Risk | Stack overflow if deep | Infinite loop if the condition never changes |
| Reads as | Close to the definition of the problem | Close to the steps a machine takes |
| Speed | Slower — call overhead per level | Usually faster |
Where recursion is the natural choice (the guide's examples)
| Use | Why it is recursive | Base case |
|---|---|---|
| Quicksort | Pick a pivot, split the list into smaller and larger items, then quicksort each part the same way | A part with 0 or 1 items is already sorted |
| Traversing a binary tree | Visit a node, then traverse its left subtree and its right subtree, each a smaller tree | An empty subtree |
| Fractal images | A shape is drawn from smaller copies of itself, e.g. each branch of a fractal tree splits into two smaller branches | A branch shorter than a set length is not split |
The honest answer on factorial: Factorial and Fibonacci are taught recursively because they are easy to show, not because recursion is the right choice for them — a loop is faster and uses constant memory.
Recursion genuinely wins where the data itself is nested: traversing a tree, walking a folder structure, parsing an expression. Saying that shows judgement.
How this is tested — you must identify both parts and explain the stack cost, not just describe self-calling. It comes up two ways:
Paper 2 — working with code
- Explain the concept of recursion, 3-4 marks
- Identify the base case in given code
- State one application of recursion
Paper 2 — the algorithmic-thinking question
- Compare recursion with iteration
- Explain why deep recursion fails
The classic trap: Saying only "a function that calls itself". That is half the definition — without a base case it never terminates, and the answer must name both parts.
Explain what recursion is, using a worked example, and state one advantage and one disadvantage against iteration.
Model answer plan
See the answer broken into clear points, with guidance on how each point earns marks.