EnglandComputer ScienceSyllabus dot point

What makes an algorithm recursive, and how does Big-O notation measure how efficiently an algorithm scales?

Recursion and algorithmic complexity: the base case and recursive case, how recursion uses the call stack, and Big-O notation for the time and space complexity of algorithms (constant, logarithmic, linear, polynomial and exponential).

An Eduqas Component 1 answer on recursion and complexity: the base case and recursive case, how recursion uses the call stack and can cause stack overflow, and Big-O notation for measuring how an algorithm's time and space scale with input size.

Generated by Claude Opus 4.814 min answerUpdated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Quick answer

A recursive algorithm is defined in terms of itself: it has a base case that stops the recursion and returns a result directly, and a recursive case that calls the function on a smaller input, moving towards the base case. Each call adds a stack frame (its parameters and return address) to the call stack; the frames pile up on the way down and are popped on the way back up, so recursion with no base case (or one never reached) causes a stack overflow. Big-O notation describes how an algorithm's running time or memory grows with the input size $n$ , keeping only the dominant term and dropping constants, so it measures scalability, not exact time. The common classes from best to worst are $O(1)$ (constant), $O(\log n)$ (logarithmic), $O(n)$ (linear), $O(n \log n)$ , $O(n^2)$ (quadratic, a polynomial) and $O(2^n)$ (exponential). Big-O lets you predict which algorithm stays fast as data grows.

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

Eduqas wants you to explain recursion (the base case and recursive case and how the call stack supports it), and use Big-O notation to describe how an algorithm's time and space scale with input size. Expect to write or trace a recursive function and to compare or order complexities.

The answer

Recursion: base case and recursive case

The call stack and stack overflow

Big-O notation and complexity classes

Examples in context

Recursion expresses tree and graph traversals, the divide-and-conquer in merge sort and quick sort, and problems like the Towers of Hanoi cleanly, though each carries the call-stack cost. Big-O is the vocabulary engineers use to choose algorithms: a feature that works on $1{,}000$ items with an $O(n^2)$ method may freeze on a million, where an $O(n \log n)$ method still responds. This is why the searching and sorting dot points always pair an algorithm with its complexity, and why functional programming (later) leans on recursion in place of loops.

Try this

Q1. State the two parts every correct recursive subroutine must have. [2 marks]

Cue. A base case (stops the recursion) and a recursive case (calls itself on input closer to the base case).

Q2. Why can deep recursion cause a stack overflow? [1 mark]

Cue. Each call pushes a frame onto the call stack; if the recursion is too deep (or has no reachable base case), the stack runs out of space.

Q3. Place in order of efficiency for large $n$ , best first: $O(n)$ , $O(1)$ , $O(n^2)$ , $O(\log n)$ . [1 mark]

Cue. $O(1)$ , $O(\log n)$ , $O(n)$ , $O(n^2)$ .

Exam-style practice questions

Practice questions written in the style of WJEC Eduqas exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Eduqas 20205 marksWrite a recursive function to calculate

n!

(n factorial), clearly identifying the base case and the recursive case, and explain how the call stack is used when the function runs.

Show worked answer →

Recursive factorial (up to 3 marks):

FUNCTION factorial(n)
    IF n <= 1 THEN
        RETURN 1            // base case
    ELSE
        RETURN n * factorial(n - 1)   // recursive case
    ENDIF
ENDFUNCTION

The base case ( $n \leq 1$ returns $1$ ) stops the recursion; the recursive case multiplies $n$ by the factorial of $n - 1$ .

Call stack (up to 2 marks): each call to factorial pushes a stack frame holding its n and return address before calling itself; the calls stack up until the base case returns, then the frames are popped in reverse, multiplying the results back up.

Markers reward the correct base and recursive cases and the description of frames being pushed on the way down and popped (with multiplication) on the way back up.

Eduqas 20224 marksExplain what Big-O notation describes, and place these complexities in order from most to least efficient for large

n

O(n^2)

O(1)

O(n \log n)

O(\log n)

Show worked answer →

Big-O describes how the running time (or memory) of an algorithm grows as the input size $n$ grows, focusing on the dominant term and ignoring constants, so it measures scalability rather than exact time (up to 2 marks).

Order from most to least efficient (up to 2 marks): $O(1)$ , then $O(\log n)$ , then $O(n \log n)$ , then $O(n^2)$ .

Markers reward the growth-rate definition (worst-case scaling, dropping constants) and the correct ordering, with $O(1)$ best and $O(n^2)$ worst of those listed.

Related dot points

Sources & how we know this

WJEC Eduqas GCE AS/A Level Computer Science specification (from 2015) — Eduqas (2015)