CAIE 9618 · Paper 4 · Topic 4.1.1

Recursion

Base Case · Recursive Case · Call Stack · Stack Overflow · Trace Tables · CAIE Pseudocode

CSZone Cambridge International AS & A Level Computer Science 9618

What is Recursion?

A Function That Calls Itself

Recursion is a programming technique where a subroutine calls itself with a modified argument, progressively reducing the problem until a base case is reached that can be solved directly — without further recursion.

TWO ESSENTIAL COMPONENTS

Base case — the terminating condition; the case that can be solved without recursion; MUST be reached eventually

Recursive case — calls the same function with a modified argument that moves closer to the base case each time

WITHOUT BASE CASE

Infinite recursion — each call adds a new frame to the call stack

Stack fills up → stack overflow → program crashes

FUNCTION Factorial(n : INTEGER) : INTEGER
IF n = 0 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1)
// recursive case
ENDIF
ENDFUNCTION

Base case: n = 0 → returns 1. Recursive case: n × Factorial(n−1). Each call decrements n → base case reached.

The Call Stack

How Recursion Executes — Factorial(4)

WINDING (calls building up)

Factorial(4) → waiting for Factorial(3)

Factorial(3) → waiting for Factorial(2)

Factorial(2) → waiting for Factorial(1)

Factorial(1) → waiting for Factorial(0)

Factorial(0) → returns 1 ← BASE CASE

Each call stores: local variables, return address. Stack grows DOWNWARD on most systems.

UNWINDING (returning values)

Factorial(0) = 1

Factorial(1) = 1 × 1 = 1

Factorial(2) = 2 × 1 = 2

Factorial(3) = 3 × 2 = 6

Factorial(4) = 4 × 6 = 24 ✓

KEY EXAM POINT

Each stack frame stores a copy of all local variables and the return address. When the function returns, the frame is removed (popped from the stack). Memory is released in LIFO order.

Recursion vs Iteration

When to Use Which?

RECURSION

Naturally suits problems with recursive structure (trees, Fibonacci, Towers of Hanoi, merge sort)

Code is often more elegant and closer to mathematical definition

Higher memory overhead — each call adds a stack frame

Risk of stack overflow for very deep recursion

Function call overhead makes it slower than iteration

ITERATION

Lower memory overhead — no new stack frames

Generally faster — no function call overhead

Better for simple counting/looping tasks

Can be less intuitive for inherently recursive problems

Note: every recursive algorithm CAN be rewritten iteratively (using an explicit stack). Some compilers perform tail-call optimisation to automatically convert tail-recursive calls into iteration.

Exam Practice

Cambridge-style questions

Question 1

The following CAIE pseudocode function computes the sum of integers from 1 to n:

FUNCTION Sum(n : INTEGER) : INTEGER
  IF n = 1 THEN RETURN 1
  ELSE RETURN n + Sum(n - 1)
  ENDIF
ENDFUNCTION

Trace the execution of Sum(4) and state the final return value. [3]

1

Sum(4) calls Sum(3), Sum(3) calls Sum(2), Sum(2) calls Sum(1) — base case returns 1.

1

Unwinding: Sum(1)=1, Sum(2)=2+1=3, Sum(3)=3+3=6, Sum(4)=4+6=10.

1

Final return value = 10.

Common Mistakes

Don't lose easy marks

1

Omitting the base case when writing a recursive function in the exam — without a base case the recursion is infinite and the answer is wrong, even if the recursive step is correct. Always identify and state the base case explicitly.

2

Saying recursion "uses a loop" — recursion does NOT use iteration. It uses function calls. The call stack manages the repetition. Confusing these two concepts loses marks in comparison questions.

3

In trace table questions, forgetting to show the unwinding phase — many students only show the calls going in (winding) but not the return values coming back out. You must show both phases to get full marks.

Topic Summary — 4.1.1

What You Need to Know

RECURSION ESSENTIALS

Function calls itself. Must have: (1) base case — terminates recursion; (2) recursive case — moves toward base case. Without base case → infinite recursion → stack overflow.

CALL STACK

Each call pushes a new stack frame (local vars + return address). Unwinds LIFO when base case hit. Stack overflow if recursion too deep.

vs ITERATION

Recursion: elegant, natural for trees/sorting, but uses more memory and has function call overhead. Iteration: faster, lower memory, no stack overflow risk. Any recursive algorithm can be written iteratively with an explicit stack.

CSZone

Next Video

4.1.2

OOP Fundamentals

Classes · Objects · Encapsulation · Constructors

Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools