Further Programming

Recursion

Functions that call themselves to solve a problem in smaller steps — a third way of repeating work that uses no loop at all. Master the factorial problem, the four essential features (base case, general case, recursive call, progress), two-phase tracing (calling + unwinding), recursive examples (denary-to-binary, count digits), recursion vs iteration trade-offs, and how the compiler uses the call stack with stack frames and unwinding.

31.1 What is Recursion? The Factorial Problem

You have already met two ways of repeating work — FOR loops and WHILE loops. Recursion is a third way of repeating work, but it does not use a loop at all. Instead, a function or procedure calls itself with a smaller version of the same problem, and keeps doing so until the problem is small enough to be solved directly.

Why are we doing this?
  • You already know that 5! means 5 × 4 × 3 × 2 × 1 = 120.
  • The factorial problem is the simplest possible example that defines itself in terms of itself: 5! is just 5 × 4!.
  • Once you see why that single observation gives you a complete algorithm, you understand recursion.
Key rule — the recursive definition of factorial
  • Factorial(n) = n × Factorial(n − 1) for any n > 0, and Factorial(0) = 1.
  • The first part is the general case, the second part is the base case.
TermMeaning
RecursionA method where a function or procedure calls itself, with each call working on a smaller version of the same problem.
Base caseThe simplest version of the problem, which can be answered directly without calling the function again. Recursion stops here.
General caseThe case where the function calls itself with a smaller input. Sometimes called the recursive step.
Recursive callThe line inside the function where it calls itself again, passing a smaller value.
Call stackAn area of memory where the computer keeps each unfinished function call. New calls are pushed on top; finished ones are popped off.
Stack frameOne entry on the call stack. It holds the parameters, local variables, and the return address for one call.
UnwindingThe phase after the base case is reached, where each call returns its value to the call that made it, one by one.
Stack overflowAn error that happens when too many calls are pushed onto the call stack — usually because the base case is missing or never reached.
IterationRepeating work using a loop (FOR, WHILE, REPEAT). The non-recursive alternative.

Iterative (loop) version:

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
   DECLARE result : INTEGER
   result <- 1
   FOR i <- 1 TO n
      result <- result * i
   NEXT i
   RETURN result
ENDFUNCTION

Recursive version:

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
   DECLARE result : INTEGER
   IF n = 0 THEN
      result <- 1                    // BASE CASE
   ELSE
      result <- n * Factorial(n - 1) // GENERAL CASE + RECURSIVE CALL
   ENDIF
   RETURN result
ENDFUNCTION

The recursive version has no loop. Notice the line result ← n * Factorial(n - 1) — the function calls itself with a smaller value. The function reads almost exactly like the mathematical formula n × (n − 1)!. Without the base case, the function would call itself forever and the call stack would overflow.

Nested calls for Factorial(4)
  • Each box is one call. A box can only finish once the box <em>inside</em> it has finished.
  • The calling phase goes outside-in; the green inner box is the base case.
  • Once it returns 1, the answers flow back outward (unwinding): 1 → 1 → 2 → 6 → 24.
Task — Worked Example — Trace Factorial(4) [6 marks]
Using the recursive Factorial function, complete a trace of Factorial(4). Show each call, whether the base case is reached, and the value returned. [6]
Hint:
  • Step 1 — Track each call as it happens (calling phase): Fact(4)→Fact(3)→Fact(2)→Fact(1)→Fact(0).
  • Step 2 — Reach the base case: Fact(0) returns 1.
  • Step 3 — Unwind: each paused call multiplies and returns (1→1→2→6→24).
Your Turn — Your Turn — Trace Factorial(5) [6 marks]
Using the same recursive Factorial function, complete the trace for Factorial(5). State the final result. [6]
Hint:
  • The calling phase has 6 rows (n = 5, 4, 3, 2, 1, 0). Then unwinding starts from the base case and works back out, multiplying each time.
Exam tip:
  • When Cambridge asks you to trace a recursive function, always lay out two phases: a calling phase where each row shows the call and the expression that is waiting, then a clearly marked unwinding phase where return values appear in reverse order.
  • Examiners award one mark for reaching the base case and one mark for the final returned value, with intermediate marks for correct return values during unwinding.

31.2 Essential Features of Recursion

Why are we doing this?
  • Cambridge exam questions on recursion very often start with: “State the essential features of a recursive routine” or “Identify three features of recursion shown by this algorithm”.
  • These are AO1 knowledge marks — easy to score if you have the list memorised.

Any recursive routine — no matter the problem it solves — must have all four of the following features. Miss one and the routine will either fail to stop, fail to produce an answer, or fail to be recursive at all.

#FeatureWhat it means
1Base caseA condition that can be solved directly without another recursive call. This is the stopping condition.
2General caseThe case where the routine calls itself, expressing the answer in terms of a smaller version of the problem.
3Recursive callThe line inside the routine where it calls itself, passing a value closer to the base case.
4Progress to base caseEach recursive call must move the input closer to the base case. Otherwise the routine never stops.
Key rule — what happens if a feature is missing
  • No base case → the function calls itself forever and the call stack overflows.
  • No general case → the function is not recursive; it is just a regular function.
  • No progress toward base case → e.g. calling Factorial(n) from inside Factorial(n). Again, infinite recursion and stack overflow.
Task — Worked Example — Identify the essential features of CountDown [3 marks]
The procedure CountDown is defined recursively. State three essential features of recursion shown in this procedure. [3]
Hint:
  • Step 1 — Find the base case (IF n = 0).
  • Step 2 — Find the general case and recursive call (ELSE, CALL CountDown(n-1)).
  • Step 3 — Check progress (n-1 moves toward 0).
Your Turn — Your Turn — Identify the features in PowerOfTwo [3 marks]
State three essential features of recursion shown in the PowerOfTwo function. [3]
Hint:
  • Look for (1) a condition that returns an answer with no further call, (2) a branch with a self-call, (3) something that decreases on each call.
Exam tip:
  • When the question says “identify” or “state” the features, you do not need long sentences.
  • One-line bullet points with the keyword (base case, general case, recursive call, progress) and a quoted line from the code are enough.
  • Examiners want to see the keyword and evidence that you can locate it in the supplied code.

31.3 Tracing Recursive Algorithms

Why are we doing this?
  • Tracing recursion is one of the most common AO2 questions on Paper 3.
  • The examiner gives you a small recursive function with a starting value and asks for the output, the return value, or both.
  • Students lose marks because they try to do it in their head.
  • The fix: always draw a two-phase trace table — calling phase, then unwinding phase.
The general method
  • Write the initial call as the first row of a table.
  • For each row, check the base case condition. If FALSE, write the expression that will be returned (with the recursive call still inside it) and add a new row for the recursive call.
  • When the base case becomes TRUE, write down the return value and draw a line to mark where unwinding starts.
  • Work back up the table. For each paused call, substitute the return value from the call below into its expression and evaluate.
Task — Worked Example — Trace SumTo(4) [5 marks]
The function SumTo adds the integers from 1 to n. Trace the call SumTo(4). State the value returned. [5]
Hint:
  • Calling phase: each call where n > 0 pauses, waiting for the next call to return.
  • Unwinding: substitute each return value back into the call above.
Your Turn — Your Turn — Trace CountDown(3) [5 marks]
Using the CountDown procedure, complete a trace of CountDown(3). Fill in the value output by each call. State the complete output. [5]
Hint:
  • This is a procedure, not a function — there is no return value. Each call outputs either n or “Blast off!”.
Exam tip:
  • Pay close attention to where the recursive call sits in the code.
  • If the call comes before any output, the outputs appear during unwinding and are in reverse order.
  • If the call comes after any output (as in CountDown), the outputs happen during the calling phase and are in natural order.
  • Students who do not check this routinely produce the right numbers in the wrong order.

31.4 More Recursive Examples

Why are we doing this?
  • Factorial is the textbook example, but examiners deliberately pick problems you have not seen before.
  • This section gives you two more recursive patterns — converting a denary number to binary, and counting digits — so that when an unfamiliar recursive routine appears in the exam, you already know how to read it.

Example 1 — Denary to binary by repeated division:

The last bit of n in binary is n MOD 2. The rest of the bits are the binary of n DIV 2. So the binary of n is DenaryToBinary(n DIV 2) with n MOD 2 stuck on the end. The base case is when n = 0 — return the empty string.

FUNCTION DenaryToBinary(n : INTEGER) RETURNS STRING
   DECLARE result : STRING
   IF n = 0 THEN
      result <- ""
   ELSE
      result <- DenaryToBinary(n DIV 2) & NUM_TO_STR(n MOD 2)
   ENDIF
   RETURN result
ENDFUNCTION
Task — Worked Example — Trace DenaryToBinary(13) [5 marks]
Trace the call DenaryToBinary(13). Show the value of n DIV 2 and n MOD 2 at each step and the final string returned. [5]
Hint:
  • At each call, compute n DIV 2 (the next n) and n MOD 2 (the bit collected). Unwind by appending each bit.
Your Turn — Your Turn — Trace DenaryToBinary(11) [5 marks]
Trace DenaryToBinary(11). Fill in the values of n DIV 2, n MOD 2, and the final string returned. [5]
Hint:
  • Keep dividing by 2. The base case is n = 0. Each n MOD 2 is the bit collected; the final string is read from the last call back up to the first.

Example 2 — Counting the digits in a positive integer:

The base case is a single-digit number (less than 10) — it has 1 digit. Otherwise, the answer is 1 + CountDigits(n DIV 10) (chop off the last digit).

FUNCTION CountDigits(n : INTEGER) RETURNS INTEGER
   IF n < 10 THEN
      RETURN 1
   ELSE
      RETURN 1 + CountDigits(n DIV 10)
   ENDIF
ENDFUNCTION

// CountDigits(4729):
// CountDigits(4729) = 1 + CountDigits(472)
// CountDigits(472)  = 1 + CountDigits(47)
// CountDigits(47)   = 1 + CountDigits(4)
// CountDigits(4)    = 1               <- base case, 4 < 10
// Unwinding: 1 -> 2 -> 3 -> 4
Exam tip:
  • Whenever a problem can be phrased as “the answer for n is some-operation-of(n) combined with the answer for a-smaller-version-of-n”, recursion will work.
  • The exam will not ask you to design a recursive routine from scratch on Paper 3 — but it will ask you to complete or trace one.

31.5 Recursion vs Iteration

Why are we doing this?
  • Anything that can be done recursively can also be done with a loop, and vice versa.
  • So why bother with recursion at all?
  • Cambridge questions ask you to compare the two approaches and to justify when each is appropriate.
Recursion — strengthsRecursion — weaknesses
Code matches the mathematical or natural definition (e.g. factorial, Fibonacci).Each call uses memory on the call stack — risk of stack overflow for deep recursion.
Often shorter and more readable for problems with self-similar structure.Slower because every call has overhead (saving and restoring stack frames).
Natural fit for recursive data structures: binary trees, linked lists, file directories.Harder for beginners to trace and debug.
Useful for divide-and-conquer algorithms (binary search, merge sort, quicksort).The same sub-problem may be solved many times (e.g. naive Fibonacci).
Iteration — strengthsIteration — weaknesses
Uses only one stack frame — no risk of stack overflow.Code can be longer and less elegant for problems with self-similar structure.
Faster: no function-call overhead per step.Awkward fit for processing trees and other branching data (a stack must be managed by hand).
Lower memory use overall.Some divide-and-conquer algorithms become much harder to express.
Easier to trace step by step using a standard trace table.—
Key rule — quick choice guide
  • Use recursion when the problem is self-similar (factorial, Fibonacci, tree traversal, divide-and-conquer).
  • Use iteration when repetitions are simple and bounded (looping through an array, totalling values, counting).
  • The safest line: “Recursion is beneficial when the problem has a recursive structure; otherwise, iteration is usually faster and uses less memory.”
Task — Worked Example — Advantages of iterative Factorial [2 marks]
A programmer has written a recursive function to calculate n! and is considering rewriting it iteratively. Give two advantages of the iterative version over the recursive version. [2]
Hint:
  • Think about what changes: memory (stack frames), speed (call overhead), stack overflow risk, traceability.
Your Turn — Your Turn — Justify a recursive tree traversal [2 marks]
A programmer is writing a routine to traverse a binary tree and output every data item in order. Give two reasons why a recursive solution might be chosen over an iterative one. [2]
Hint:
  • Think about how a binary tree is built (each node has subtrees) and how that matches a routine that calls itself on each subtree.
Exam tip:
  • When asked to “compare” or “give advantages and disadvantages”, do not write vague things like “recursion is more elegant” — that earns nothing.
  • State the technical reason: memory, stack frames, execution speed, stack overflow, code length, matching a recursive data structure.
  • One technical reason equals one mark.

31.6 Compiler & Stack — How Recursion Really Runs

Why are we doing this?
  • Cambridge specifically lists “use of stacks and unwinding” in the syllabus.
  • Examiners ask you to explain what the compiler does when a recursive routine runs — and the answer is always the same: it uses a stack to remember each paused call.

When any function or procedure is called, the computer needs to remember three things so it can resume the calling code afterwards: the values of the parameters passed in, the local variables created inside the function, and the return address — where in the calling code to come back to. This bundle is called a stack frame. The compiler pushes a new stack frame onto the call stack every time a function is called, and pops it off again when the function returns. For a recursive call, several frames pile up — one per pending call.

Key rule — what the compiler does for a recursive call
  • Push a new stack frame containing the current parameter, any local variables, and the return address.
  • Execute the body of the function with the new parameter.
  • If the base case is met, calculate the return value.
  • If not, push another frame and repeat from step 1.
  • When a function returns, pop its frame off the stack and pass the return value back to the call that was waiting (unwinding).
Task — Worked Example — Describe what the compiler does [4 marks]
A recursive function Factorial is called with the value 4. Describe the steps the compiled program takes, with reference to the call stack. [4]
Hint:
  • Step 1 — On each call, a frame is pushed (parameter, local vars, return address).
  • Step 2 — Base case provides the first real return value (frame popped).
  • Step 3 — Unwinding pops one frame at a time, passing values back.
Your Turn — Your Turn — Stack overflow explained [3 marks]
A recursive function has been written without a base case. Explain what will happen when it runs and why. [3]
Hint:
  • Think about what a missing base case does — what stops the pushing?
Exam tip:
  • Examiners reward the specific vocabulary: stack frame, pushed onto the stack, popped off, base case, unwinding, return address.
  • Use these exact words.
  • A vague answer like “the program remembers each call and reverses them at the end” is unlikely to score full marks, even if the meaning is right.

31.7 Full Exam-Style Questions

Paper 3 · recursion · ~18 marks Four Cambridge-style questions on essential features, Fibonacci, PrintReverse, and the compiler stack.

Q1 (a) [2] Define the term recursion. (b) [2] State two essential features that every recursive routine must contain.

Q2 (a) [1] A function Mystery is defined as Mystery(n) = Mystery(n-1) + Mystery(n-2) with base case n ≤ 1 returns n. State the value returned by Mystery(4). (b) [1] State the sequence for arguments 0, 1, 2, 3, 4, 5. (c) [1] State the name commonly given to this sequence.

Q3 (a) [2] PrintReverse(n) outputs n MOD 10 then, if n ≥ 10, calls PrintReverse(n DIV 10). State the output of PrintReverse(347). (b) [1] Identify the base case. (c) [2] Explain why the output is in reverse order.

Q4 (a) [4] Describe how a compiler uses a stack to handle a recursive function. Refer to the call stack, stack frames, and unwinding. (b) [2] Explain what is meant by a stack overflow and one reason why a recursive function might cause one.

Lab Task — Show full mark scheme
Reveal the mark scheme for all four exam-style questions.
Hint:
  • Q1: recursion = calls itself with smaller problem until base case; features = base case + general case + progress.
  • Q2: Mystery(4) = 3; sequence = 0,1,1,2,3,5; Fibonacci.
  • Q3: output 7 4 3; base case n < 10; reverse because OUTPUT comes before the recursive call.
  • Q4: push frame per call (params, locals, return addr); base case returns; pop + unwind; stack overflow = too many frames, no base case or no progress.

✓ Key Points Summary

Recursion is a method where a function or procedure calls itself, with each call working on a smaller version of the same problem, until a base case is reached.
The four essential features: (1) a base case (stopping condition), (2) a general case (calls itself), (3) a recursive call (the self-call line), (4) progress toward the base case (input moves closer each call).
Without a base case, the function calls itself forever and the call stack overflows. Without progress, the same thing happens (infinite recursion).
The recursive definition of factorial: Factorial(n) = n × Factorial(n-1) for n > 0 (general case), Factorial(0) = 1 (base case).
A recursive trace has two phases: the calling phase (calls descend to the base case, each pausing) and the unwinding phase (returns climb back up, each paused call computing and returning).
If the recursive call comes BEFORE the output, outputs appear in reverse order during unwinding. If it comes AFTER (like CountDown), outputs appear in natural order during the calling phase.
SumTo(n) = n + SumTo(n-1) with SumTo(0) = 0. SumTo(4) = 10 (1+2+3+4).
DenaryToBinary(n) = DenaryToBinary(n DIV 2) & NUM_TO_STR(n MOD 2) with base case n = 0 returns "". DenaryToBinary(13) = "1101".
CountDigits(n) = 1 + CountDigits(n DIV 10) with base case n < 10 returns 1. CountDigits(4729) = 4.
Recursion is beneficial when the problem is self-similar (factorial, Fibonacci, tree traversal, divide-and-conquer) or the data structure is recursive (binary trees).
Iteration is beneficial when repetitions are simple and bounded — it is faster (no call overhead), uses less memory (one stack frame), and has no stack overflow risk.
A weakness of recursion: each call uses memory on the call stack (risk of stack overflow for deep recursion); slower due to call overhead; the same sub-problem may be solved many times (naive Fibonacci).
A stack frame is one entry on the call stack: it holds the parameters, local variables, and the return address for one call.
When a function is called, a new stack frame is pushed. When it returns, the frame is popped and the return value is passed back to the waiting call (unwinding).
A stack overflow occurs when too many calls are pushed onto the call stack — usually because the base case is missing, never reached, or the recursion is too deep.
Examiners reward specific vocabulary: stack frame, pushed onto the stack, popped off, base case, unwinding, return address. Use these exact words.

31.8 Practice Tasks

Fifteen exam-style tasks. Click Hint for bullet-point guidance, then Help to reveal a worked solution.

1Practice Task — Define recursion [2 marks]
Define the term recursion.
2Practice Task — Essential features [3 marks]
State three essential features of a recursive routine.
3Practice Task — Trace Factorial(4) [6 marks]
Trace the recursive Factorial(4). Show each call, the base case, and the return values during unwinding.
4Practice Task — Trace Factorial(5) [6 marks]
Trace Factorial(5). State the final result.
5Practice Task — Trace SumTo(4) [5 marks]
Trace SumTo(4) where SumTo(n) = n + SumTo(n-1), SumTo(0) = 0. State the value returned.
6Practice Task — Trace CountDown(3) [5 marks]
Trace CountDown(3). State the complete output.
7Practice Task — Trace DenaryToBinary(13) [5 marks]
Trace DenaryToBinary(13). Show n DIV 2 and n MOD 2 at each step and the final string.
8Practice Task — Trace DenaryToBinary(11) [5 marks]
Trace DenaryToBinary(11). State the final string.
9Practice Task — CountDigits(4729) [4 marks]
Trace CountDigits(4729) where base: n < 10 returns 1, else 1 + CountDigits(n DIV 10). State the final answer.
10Practice Task — Mystery/Fibonacci [3 marks]
Mystery(n) = Mystery(n-1) + Mystery(n-2), base n ≤ 1 returns n. State Mystery(4), the sequence for 0-5, and the name.
11Practice Task — PrintReverse(347) [5 marks]
PrintReverse(n) outputs n MOD 10, then if n >= 10 calls PrintReverse(n DIV 10). (a) State output of PrintReverse(347). (b) Identify the base case. (c) Explain why the output is in reverse order.
12Practice Task — Advantages of iteration [2 marks]
Give two advantages of an iterative Factorial over a recursive one.
13Practice Task — Justify recursion for tree traversal [2 marks]
Give two reasons why a recursive solution might be chosen over an iterative one for traversing a binary tree.
14Practice Task — Describe the compiler's use of the stack [4 marks]
Describe how a compiler uses a stack to handle a recursive function. Refer to the call stack, stack frames, and unwinding.
15Practice Task — Stack overflow [3 marks]
Explain what a stack overflow is and one reason why a recursive function might cause one.

Question Bank

Answer all questions, then press Submit Quiz to see your score.

0/12 answered

Question 1Multiple Choice

Recursion is:

Question 2Multiple Choice

The base case of a recursive routine is:

Question 3True / False

Every recursive routine must have a base case, a general case, a recursive call, and progress toward the base case.

Question 4Multiple Choice

Factorial(4) returns:

Question 5Multiple Choice

What are the two phases of a recursive trace?

Question 6Multiple Choice

SumTo(4) returns: (SumTo(n) = n + SumTo(n-1), SumTo(0) = 0)

Question 7True / False

If the recursive call comes before the output, outputs appear in reverse order during unwinding.

Question 8Multiple Choice

DenaryToBinary(13) returns:

Question 9Multiple Choice

CountDigits(4729) returns: (base: n < 10 returns 1; else 1 + CountDigits(n DIV 10))

Question 10Multiple Choice

A weakness of recursion vs iteration is:

Question 11Multiple Choice

What is a stack frame?

Question 12True / False

A stack overflow occurs when too many calls are pushed onto the call stack — usually because the base case is missing or never reached.

Answer all 12 questions to enable submission.