AQA A-Level Computer Science Paper 2, June 2025: Question 11

6 marks · Medium difficulty · Short Answer

Analyze a functional recursive Fibonacci function, determine its properties and type, explain its computational inefficiency, and describe partial function application.

Practise this question

Question

Question text

11 The Fibonacci sequence is a number sequence in which the first two numbers are

both 1 and every other number in the sequence is the sum of the previous two

numbers. The first ten values in the Fibonacci sequence are:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Figure 6 shows a function written in a functional programming language to calculate

the nth term in the Fibonacci sequence.

Figure 6

fibonacci 1 = 1

fibonacci 2 = 1

fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)

11.1 Shade all of the lozenges for the statements that are true about the fibonacci

function in Figure 6.

[1 mark]

A The function has one argument.

B The function is a first-class object.

C The function outputs a list.

D The function uses a higher-order function.

11.2 Shade one lozenge to indicate the function type of the fibonacci function

in Figure 6.

[1 mark]

A ℕ → ℕ

B ℚ → ℤ

C ℝ → ℤ

D ℤ → ℕ 29

11.3 Explain why the recursive method used by the code in Figure 6 is not an efficient

method of calculating the nth term in the Fibonacci sequence.

[2 marks]

11.4 Describe what partial function application is.

[2 marks]

Mark scheme

Show the mark scheme

Total

Qu Pt Marking guidance

marks

11 1 Mark is AO2 (analyse) 1

1 mark if lozenges A and B both shaded:

A (The function has one argument)

B (The function is a first-class object)

R. if the number of shaded lozenges is not two

Total

Qu Pt Marking guidance

marks

11 2 Mark is AO2 (analyse) 1

A; (ℕ → ℕ)

R. if more than one lozenge shaded

Total

Qu Pt Marking guidance

marks

11 3 Marks are AO2 (analyse) 2

Each application of the function generates two further applications of the same

function;

A. the function calls itself twice

The function may (A. will) be applied to the same argument multiple times;

A. the same value is calculated multiple times

A. (some of) the Fibonacci numbers will be calculated multiple times

The number of applications // memory requirements of the function grow

exponentially (with the position of the number in the Fibonacci sequence) // the

function has big-O complexity O(2n) // the function has exponential time

complexity;

A. an

R. responses relating to the problem rather than the function–A-LEVELCOMPUTER SCIENCE – –

Max 2

Total

Qu Pt Marking guidance

marks

11 4 Marks are AO1 (understanding) 2

2 marks for making all three points from this list or 1 mark for making one or

two points from the list:

• one (or more) argument(s) to a function are fixed

A. function is applied to one/some of its arguments

R. function applied to its arguments

• creating a new function

• with fewer arguments // that takes the remaining arguments.

Accept descriptions of functions with a specific number of arguments assumed by

the student, for example:

• one of the arguments of a three-argument function is fixed

• creating a new function

• with two arguments.

How to answer it

Functional Programming & Recursive Fibonacci

What this question tests

This question assesses your understanding of functional programming concepts and algorithm analysis:

Characteristics of functional programming: First-class objects, function arguments, and higher-order functions.
Type signatures & set notation: Mapping between mathematical sets (natural numbers ℕ, integers ℤ, rationals ℚ, reals ℝ).
Algorithmic complexity of tree recursion: Explaining why naive recursive Fibonacci exhibits exponential time complexity O(2ⁿ) and redundant evaluations.
Partial function application: Defining the process of fixing some arguments of a function to yield a new function of lower arity.

Question 11.1

Properties of the Functional Fibonacci Function

1 Mark • AO2 (Analyse)

✅ Correct Answer

Shade both of the following lozenges:

A: The function has one argument.
B: The function is a first-class object.

💡 Key Knowledge

One argument: The definition pattern is fibonacci n . Only a single parameter n is passed.
First-class object: In functional languages, all functions are first-class objects (they can be passed as arguments, assigned to variables, and returned from functions).
Not a higher-order function: It neither accepts another function as an argument nor returns a function.
Output: It outputs a single integer, not a list.

❌ Common Errors & Examiner Traps

Shading only one lozenge: The question states "Shade all of the lozenges that are true". The mark scheme explicitly states: "Reject if the number of shaded lozenges is not two." Selecting only A or only B scores 0 marks.
Confusing the function with higher-order functions: Because fibonacci calls itself recursively, students incorrectly assume it must be higher-order. Recursion is not higher-order application.

Mark Scheme Rule: 1 mark strictly awarded if and only if both A and B are shaded.

Question 11.2

Function Type Signature

1 Mark • AO2 (Analyse)

✅ Correct Answer

Shade lozenge A: ℕ → ℕ

💡 Mathematical Sets in CS

ℕ (Natural numbers): Positive whole counting numbers {1, 2, 3, ...} (or non-negative whole numbers). Term positions 1st, 2nd, 3rd, ... and the Fibonacci values {1, 1, 2, 3, 5, ...} are all natural numbers.
ℤ: Integers (includes negative whole numbers).
ℚ: Rational numbers (fractions/ratios).
ℝ: Real numbers (continuous values including irrationals).

🧠 Exam Technique

Look at the domain (inputs) and codomain (outputs):

Input: The term index n must be a positive integer (e.g. 1st term, 2nd term) → Domain is ℕ.
Output: Every Fibonacci value produced is a positive integer → Codomain is ℕ.
This immediately rules out B, C, and D.

Mark Scheme Rule: 1 mark for selecting A. Reject if more than one lozenge is shaded.

Question 11.3

Inefficiency of Naive Recursive Fibonacci

2 Marks • AO2 (Analyse)

✅ Correct Answers (Any TWO points for 2 marks)

Point 1 (Branching calls): The function calls itself twice for each invocation (each application generates two further applications).
Point 2 (Redundant recomputation): The same function calls / same Fibonacci terms are calculated multiple times redundantly.
Point 3 (Exponential growth): The time complexity / number of calls / memory requirements grow exponentially: O(2ⁿ).

📐 Visualising the Call Tree (n = 5)

Notice how identical sub-trees are re-evaluated:

fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ fib(2) fib(1)

fib(3) is evaluated twice; fib(2) is evaluated three times!

❌ Common Misconceptions & Penalties

Talking about the Fibonacci sequence instead of the algorithm: The mark scheme explicitly states: "Reject responses relating to the problem rather than the function." Saying "the numbers get very big very quickly" scores 0. Focus on call overhead and duplicate evaluations.
Vague inefficiency claims: Merely writing "it uses a lot of memory" or "it is slow" without stating why (e.g. repeated calculations, calls itself twice, or exponential complexity) fails to score.

Mark Scheme Breakdown: Maximum 2 marks. 1 mark per distinct point (calls itself twice / recalculates identical subproblems / exponential O(2ⁿ) complexity).

Question 11.4

Partial Function Application

2 Marks • AO1 (Knowledge & Understanding)

✅ Model Answer Structure

Partial function application is where:

One or more arguments of a function are fixed (or supplied),
thereby creating a new function,
that takes the remaining (fewer) arguments.

💡 Concrete Example

Consider an addition function with two arguments:

add x y = x + y

Fixing x = 5 gives:

addFive = add 5

addFive is a new function taking only one remaining argument.

🧠 How the 2 Marks are Awarded

2 marks: Awarded for covering all three criteria: (1) fixing some arguments, (2) resulting in a new function, (3) which accepts fewer/the remaining arguments.
1 mark: Awarded if you only include one or two of these key points.
Specific numbers accepted: You can explain with a concrete case: "Giving 1 argument to a 3-argument function to create a new function that takes the other 2 arguments."
Crucial distinction: You must state that some arguments are applied. Stating simply that a "function is applied to its arguments" is rejected because that describes normal evaluation, not partial application.

Mark Scheme Summary:
• 2 marks: All 3 marking points included.
• 1 mark: 1 or 2 marking points included.
• Reject: "function applied to its arguments" (must specify one/some are fixed).

Topics

4.1 Fundamentals of programming · 4.4 Theory of computation · 4.12 Fundamentals of functional programming · 4.1.1 Programming · 4.4.4 Classification of algorithms · 4.12.1 Functional programming paradigm · 4.12.2 Writing functional programs

Question and mark scheme from the AQA A-Level Computer Science examination, Paper 2, June 2025. QuestionVault is an independent revision resource; questions remain the copyright of the awarding body.