Computer Science 9618/42 — October/November 2021

Cambridge A-Level · Practical · worked solutions for every part, with the mark scheme

questions

marks

150

minutes

Topics Programming Paradigms (Procedural and Object-oriented) · Recursion · Algorithms and Abstract Data Types · File Processing and Exception Handling

Q1RecursionProgramming Paradigms (Procedural and Object-oriented)Free sample

Study the following pseudocode for a recursive function.

FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER
 IF X < Y THEN
  OUTPUT X + Y
  RETURN (Unknown(X + 1, Y) * 2)
 ELSE
  IF X = Y THEN
   RETURN 1
  ELSE
   OUTPUT X + Y
   RETURN (Unknown(X - 1, Y) DIV 2)
  ENDIF
 ENDIF
ENDFUNCTION

The operator DIV returns the integer value after division e.g. 13 DIV 2 would give 6

(a)

Write program code to declare the function Unknown().

Save your program as question 1.

Copy and paste the program code into part 1(a) in the evidence document.

DifficultyMedium-Easy

Worked solution

Answer

def Unknown(X, Y):
    if X < Y:
        print(X + Y)
        return Unknown(X + 1, Y) * 2
    elif X == Y:
        return 1
    else:
        print(X + Y)
        return Unknown(X - 1, Y) // 2

Final answer

See program code

Detailed explanation

Background Concept

A recursive function is a function that calls itself. For recursion to work correctly, there must be:

a base case that stops the recursion
one or more recursive cases that move the data towards that base case

In this function, the base case is when X == Y, because the function returns 1 immediately and does not call itself again.

The two recursive cases are:

if X < Y, output X + Y, then call the function again with X + 1
if X > Y, output X + Y, then call the function again with X - 1

So each recursive call moves X one step closer to Y.

When translating pseudocode into Python:

FUNCTION ... RETURNS INTEGER becomes def ...:
IF / ELSE / ENDIF becomes Python indentation with if, elif, else
OUTPUT becomes print()
RETURN stays return
DIV becomes // for integer division

Understanding the Question

You are given a recursive function in pseudocode and asked to declare it in program code. That means you must write the real Python version of the same function, keeping the same logic, the same parameter order, the same printed outputs, and the same returned values.

The important thing is that this function does two things:

it prints values during the recursion
it returns a final integer value

Both behaviours must be preserved.

Approach

The best approach is to translate each pseudocode branch directly:

Write the function header as def Unknown(X, Y):
Convert the first condition X < Y
Convert the base case X == Y
Convert the remaining else case for X > Y
Replace DIV with Python integer division //

Using elif X == Y is the cleanest Python equivalent to the nested IF X = Y THEN inside the pseudocode.

Step-by-Step Reasoning

The pseudocode says:

If X < Y:
- output X + Y
- return Unknown(X + 1, Y) * 2

In Python, that becomes:

if X < Y:
    print(X + Y)
    return Unknown(X + 1, Y) * 2

Next, the pseudocode says:

Else, if X = Y:
- return 1

That becomes:

elif X == Y:
    return 1

Finally, the last branch is when X > Y:

output X + Y
return Unknown(X - 1, Y) DIV 2

In Python, integer division is written as //, so this becomes:

else:
    print(X + Y)
    return Unknown(X - 1, Y) // 2

Putting the three parts together gives the complete function.

Notice that the print() must happen before the recursive call in both recursive branches, because that is exactly what the pseudocode does.

Key Takeaways

A recursive function must have a base case.
Each recursive call should move the data closer to that base case.
When converting pseudocode to Python, preserve both the logic and the order of actions.
DIV in pseudocode corresponds to // in Python for integer division.

Common Mistakes

Using / instead of // for DIV. / gives floating-point division, which is not what the pseudocode specifies.
Forgetting the base case X == Y. Without it, the recursion would not stop correctly.
Printing after the recursive call instead of before it. That changes the output order.
Changing X + 1 or X - 1 incorrectly, which breaks the logic of moving towards Y.

Things to Be Careful About

Keep the function name exactly as Unknown if that is what the rest of the program uses.
Keep the parameter order as X, Y.
Python uses == for comparison, not =.
Indentation matters in Python; the return and print statements must be inside the correct branch.
Use // only because the question defines DIV as integer division.

Techniques used

translate pseudocode branches into Python if-elif-else statementsimplement a recursive function with a base case and recursive casesmap pseudocode OUTPUT and DIV to Python print and integer division

(b)

The main program needs to run all three of the following function calls and output the result of each call:

Unknown(10, 15)
Unknown(10, 10)
Unknown(15, 10)

(i)

For each of the three function calls, the main program needs to:

output the value of the two parameters
call the function with those parameters
output the return value.

Write the program code for the main program.

Save your program.

Copy and paste the program code into part 1(b)(i) in the evidence document.

DifficultyMedium-Easy

Worked solution

Answer

print("Parameters:", 10, 15)
Result = Unknown(10, 15)
print("Return value:", Result)

print("Parameters:", 10, 10)
Result = Unknown(10, 10)
print("Return value:", Result)

print("Parameters:", 15, 10)
Result = Unknown(15, 10)
print("Return value:", Result)

Final answer

See program code

Detailed explanation

Background Concept

A main program often does three separate jobs when working with functions:

prepare or show the input values
call the function
output the returned value

A function call can also have side effects. Here, Unknown() does not just return a value: it also prints values during the call. That means the console output from the function appears before the main program prints the final returned result.

Understanding the Question

You are told to run exactly these three calls:

Unknown(10, 15)
Unknown(10, 10)
Unknown(15, 10)

For each one, the main program must:

output the two parameter values
call the function
output the return value

So the answer must contain three separate call blocks, one for each parameter pair.

Approach

For each call:

Print the parameter values.
Call Unknown() with those values.
Store the returned value in a variable such as Result.
Print the returned value.

Using a variable makes the order very clear and matches what the task asks for.

Step-by-Step Reasoning

For the first call:

print("Parameters:", 10, 15)
Result = Unknown(10, 15)
print("Return value:", Result)

The first line outputs the two parameter values.
The second line calls the function.
While that function runs, it may print extra values because of the print() statements inside Unknown().
When the function finishes, its returned value is stored in Result.
The final line outputs that returned value.

The same pattern is then repeated for (10, 10) and (15, 10).

This is exactly what the question asks for: parameter output, function call, return-value output.

Key Takeaways

A function can both print values and return a value.
The main program should clearly separate input display, function call, and result display.
Repeating a consistent pattern for multiple test calls makes the program easy to follow.

Common Mistakes

Calling the function but not printing the return value.
Printing only one parameter instead of both.
Missing one of the three required calls.
Confusing values printed inside the function with the actual returned result.

Things to Be Careful About

Use the exact parameter pairs given in the question.
Keep the order of parameters correct: X first, Y second.
If you print the function call directly inside print(), the output is still valid, but storing the result first makes the sequence clearer.
Remember that the output produced inside Unknown() will appear between the parameter line and the return-value line.

Techniques used

call a function with fixed parameter valuesstore returned values in a variableoutput parameter values and function results in sequence

(ii)

Take a screenshot to show the output from part (b)(i).

Copy and paste the screenshot into part 1(b)(ii) in the evidence document.

DifficultyMedium

Worked solution

Answer

Using the parameter pairs (10, 15), (10, 10) and (15, 10), the expected console output is:

Parameters: 10 15
25
26
27
28
29
Return value: 32
Parameters: 10 10
Return value: 1
Parameters: 15 10
25
24
23
22
21
Return value: 0

Final answer

See expected console output

Detailed explanation

Background Concept

When tracing a recursive function, you must keep track of two separate things:

what is printed during the descent into deeper calls
what value is returned during the unwind back to the original call

In this function, output happens before the recursive call in each recursive branch. That means the printed values appear in descending order of calls, not when the recursion is finishing.

The base case is X == Y, which returns 1.

Then:

for X < Y, each earlier call multiplies the returned value by 2
for X > Y, each earlier call divides the returned value by 2 using integer division

Understanding the Question

The exam asks for a screenshot of the output produced by the main program from part (b)(i). Since a screenshot cannot be provided here, the correct response is the exact text that would appear on the console.

That output must include:

the parameter lines printed by the main program
the intermediate values printed inside Unknown()
the final return value printed by the main program

Approach

Handle the three calls one at a time:

Trace what the function prints.
Find the base case.
Work back out to calculate the returned value.
Combine that with the parameter line and the final Return value: line.

Step-by-Step Reasoning

For Unknown(10, 15):

10 < 15, so print 25 and call Unknown(11, 15)
11 < 15, so print 26 and call Unknown(12, 15)
12 < 15, so print 27 and call Unknown(13, 15)
13 < 15, so print 28 and call Unknown(14, 15)
14 < 15, so print 29 and call Unknown(15, 15)
15 == 15, so return 1

Now unwind:

previous call returns 1 * 2 = 2
then 2 * 2 = 4
then 4 * 2 = 8
then 8 * 2 = 16
then 16 * 2 = 32

So the first call prints 25 26 27 28 29 on separate lines and finally returns 32.

For Unknown(10, 10):

X == Y immediately
nothing is printed inside the function
it returns 1

For Unknown(15, 10):

15 > 10, so print 25 and call Unknown(14, 10)
14 > 10, so print 24 and call Unknown(13, 10)
13 > 10, so print 23 and call Unknown(12, 10)
12 > 10, so print 22 and call Unknown(11, 10)
11 > 10, so print 21 and call Unknown(10, 10)
10 == 10, so return 1

Now unwind with integer division:

previous call returns 1 // 2 = 0
then 0 // 2 = 0
then 0 // 2 = 0
then 0 // 2 = 0
then 0 // 2 = 0

So the final returned value is 0.

Putting the parameter lines and result lines around those traces gives the complete console output shown in the answer.

Key Takeaways

Trace both printed output and returned values separately in recursive questions.
The base case controls where recursion stops.
Multiplication or division on the return path happens while the recursion unwinds.
Integer division can quickly reduce a result to 0.

Common Mistakes

Forgetting that the function prints values before making the recursive call.
Writing the correct return value but missing the intermediate printed values.
Treating DIV as normal decimal division instead of integer division.
Missing that Unknown(10, 10) prints nothing inside the function.

Things to Be Careful About

Console output order matters exactly.
Each printed number appears on its own line because print() is used.
Return value: is printed only after the function has completely finished.
For Unknown(15, 10), once the first unwind gives 0, every later // 2 remains 0.

Techniques used

trace recursive calls until the base case is reacheddetermine the order of printed outputs during function executionevaluate returned values while unwinding recursion

(c)

Rewrite the function Unknown() as an iterative function, IterativeUnknown().

Save your program.

Copy and paste the program code into part 1(c) in the evidence document.

DifficultyMedium-Hard

Worked solution

Answer

def IterativeUnknown(X, Y):
    Result = 1

    if X < Y:
        while X < Y:
            print(X + Y)
            Result = Result * 2
            X += 1
        return Result
    elif X == Y:
        return 1
    else:
        while X > Y:
            print(X + Y)
            Result = Result // 2
            X -= 1
        return Result

Final answer

See program code

Detailed explanation

Background Concept

Recursion and iteration are two different ways to repeat a process.

Recursion repeats by calling the function again.
Iteration repeats by using a loop such as while.

To rewrite a recursive function iteratively, you need to identify:

the stopping condition
the state that changes each time
any value that is built up across calls

In the recursive Unknown() function:

the stopping condition is X == Y
the changing state is X
the final result is built from the base value 1
the function also prints X + Y on each step before the recursive call

Understanding the Question

You are asked to rewrite Unknown() as an iterative function called IterativeUnknown(). That means the new version must behave the same as the recursive version, but it must use loops instead of self-calls.

To be correct, the iterative version must:

return the same values as Unknown()
print the same intermediate values in the same order
handle all three cases: X < Y, X == Y, and X > Y

Approach

A good way to think about this function is:

if X < Y, X moves upward one step at a time until it reaches Y
if X > Y, X moves downward one step at a time until it reaches Y
when X == Y, the recursive version returns 1

That suggests using:

a while X < Y loop for the first recursive branch
a while X > Y loop for the second recursive branch
a direct return 1 for the base case

Because the recursive base case returns 1, the iterative version should also start with Result = 1.

Then:

in the X < Y branch, multiply Result by 2 each step
in the X > Y branch, divide Result by 2 using integer division each step

Step-by-Step Reasoning

Start with:

def IterativeUnknown(X, Y):
    Result = 1

Result starts at 1 because that is the value the recursive version eventually gets from the base case.

Case 1: `X < Y`

In the recursive version, each step does:

print X + Y
call again with X + 1
multiply the returned value by 2

Iteratively, that becomes:

if X < Y:
    while X < Y:
        print(X + Y)
        Result = Result * 2
        X += 1
    return Result

Why this works:

print(X + Y) preserves the same output as the recursive version
Result = Result * 2 captures the effect of each recursive level on the final answer
X += 1 moves X towards Y
the loop stops exactly when X == Y

For example, with (10, 15), the loop runs 5 times, so Result becomes 1 → 2 → 4 → 8 → 16 → 32.

Case 2: `X == Y`

This is the base case, so:

elif X == Y:
    return 1

This matches the original function exactly.

Case 3: `X > Y`

In the recursive version, each step does:

print X + Y
call again with X - 1
divide the returned value by 2 using integer division

Iteratively, that becomes:

else:
    while X > Y:
        print(X + Y)
        Result = Result // 2
        X -= 1
    return Result

Why this works:

print(X + Y) keeps the same output behaviour
Result = Result // 2 models the effect of each recursive unwind step
X -= 1 moves X towards Y
the loop stops when X == Y

For example, with (15, 10), Result goes from 1 to 0 on the first division, and then stays 0.

So the iterative function gives the same answers and printed outputs as the recursive one.

Key Takeaways

To convert recursion to iteration, identify the changing state and the base case.
Use a loop to move the state toward the stopping condition.
If the recursive version builds a return value, use an accumulator variable such as Result.
Preserve any side effects such as print() statements in the correct order.

Common Mistakes

Forgetting to update X inside the loop, causing an infinite loop.
Returning 1 at the end of the loop instead of returning the accumulated Result.
Omitting the print(X + Y) statements, which changes the behaviour.
Using / instead of // in the X > Y branch.
Using the wrong loop condition, such as while X != Y, without handling the direction properly.

Things to Be Careful About

The branch for X < Y must increase X; the branch for X > Y must decrease X.
Result must start at 1, not 0, because the recursive base case returns 1.
Keep the function name exactly as IterativeUnknown() because later parts call that name.
Make sure the printed values come before the update of X, matching the recursive version's order.

Techniques used

replace recursive calls with while loopsmaintain an accumulator for the final return valueupdate parameter values iteratively until the base condition is reachedpreserve the same printed outputs as the recursive version

(d)

The iterative function needs to be called three times with the same parameters as in part (b).

(i)

For each of the three function calls, the main program needs to:

output the value of the two parameters
call the iterative function with those parameters
output the return value.

Amend the main program to perform these tasks.

Save your program.

Copy and paste the program code into part 1(d)(i) in the evidence document.

DifficultyEasy

Worked solution

Answer

print("Parameters:", 10, 15)
Result = Unknown(10, 15)
print("Unknown return value:", Result)
print("Parameters:", 10, 15)
Result = IterativeUnknown(10, 15)
print("IterativeUnknown return value:", Result)

print("Parameters:", 10, 10)
Result = Unknown(10, 10)
print("Unknown return value:", Result)
print("Parameters:", 10, 10)
Result = IterativeUnknown(10, 10)
print("IterativeUnknown return value:", Result)

print("Parameters:", 15, 10)
Result = Unknown(15, 10)
print("Unknown return value:", Result)
print("Parameters:", 15, 10)
Result = IterativeUnknown(15, 10)
print("IterativeUnknown return value:", Result)

Final answer

See program code

Detailed explanation

Background Concept

A main program can be used to compare two functions by calling both with the same inputs and displaying their outputs. This is a common testing technique when you rewrite code, because it lets you check that the new version behaves the same as the original one.

Here, IterativeUnknown() is supposed to be an iterative version of Unknown(), so both functions should produce the same final results for the same parameter pairs.

Understanding the Question

You are asked to amend the main program so that the iterative function is also called three times with the same parameters used earlier:

(10, 15)
(10, 10)
(15, 10)

For each of these calls, the program must:

output the two parameter values
call the iterative function
output the returned value

Because this is an amendment to the existing main program, the simplest full answer is to show the whole updated main program containing both the recursive and iterative calls.

Approach

For each parameter pair:

Run the original Unknown() function and print its result.
Run IterativeUnknown() with the same parameters and print its result.

Using the same pattern repeatedly makes it easy to compare the two functions.

Step-by-Step Reasoning

For the first parameter pair:

print("Parameters:", 10, 15)
Result = Unknown(10, 15)
print("Unknown return value:", Result)
print("Parameters:", 10, 15)
Result = IterativeUnknown(10, 15)
print("IterativeUnknown return value:", Result)

This shows:

the parameter values before the recursive call
the recursive result
the same parameter values before the iterative call
the iterative result

The same structure is then repeated for (10, 10) and (15, 10).

This makes the console output suitable for part (d)(ii), because it clearly shows both functions for each set of parameters.

Key Takeaways

When comparing two versions of a function, call both with identical inputs.
Output labels help distinguish which result came from which function.
Repeating a consistent test structure makes checking correctness easier.

Common Mistakes

Adding only the iterative calls and accidentally removing the original recursive calls.
Calling IterativeUnknown() with the wrong parameter order.
Forgetting to print the iterative return value.
Using different labels so the output becomes unclear.

Things to Be Careful About

IterativeUnknown() must already have been declared before the main program uses it.
Keep the same three parameter pairs exactly.
Make sure the output labels clearly distinguish Unknown from IterativeUnknown.
The function calls themselves will also print intermediate values, so the console output will contain more than just the final results.

Techniques used

call both functions with the same parameter setsstore each returned value before printing itamend the main program by adding iterative function calls

(ii)

Take one or more screenshots to show the output of both functions for each set of parameters.

Copy and paste the screenshot(s) into part 1(d)(ii) in the evidence document.

DifficultyMedium-Easy

Worked solution

Answer

Using the parameter pairs (10, 15), (10, 10) and (15, 10), the expected console output is:

Parameters: 10 15
25
26
27
28
29
Unknown return value: 32
Parameters: 10 15
25
26
27
28
29
IterativeUnknown return value: 32
Parameters: 10 10
Unknown return value: 1
Parameters: 10 10
IterativeUnknown return value: 1
Parameters: 15 10
25
24
23
22
21
Unknown return value: 0
Parameters: 15 10
25
24
23
22
21
IterativeUnknown return value: 0

Final answer

See expected console output

Detailed explanation

Background Concept

A good way to verify that an iterative rewrite is correct is to run both the original recursive version and the new iterative version with the same test data, then compare their outputs.

If the iterative function is truly equivalent, it should:

print the same intermediate values
return the same final value

for every matching input.

Understanding the Question

The question asks for screenshots showing the output of both functions for each parameter set. In text form, that means you must give the exact console output produced when the amended main program from part (d)(i) runs.

Because the main program calls both functions, the console output includes:

parameter lines from the main program
printed values from Unknown()
the final recursive result line
another parameter line
printed values from IterativeUnknown()
the final iterative result line

for each parameter set.

Approach

Trace each parameter pair in order.

For each pair:

Work out the output from Unknown().
Use the fact that IterativeUnknown() behaves the same way.
Place the output in the same order that the main program executes the statements.

Step-by-Step Reasoning

For (10, 15):

Unknown(10, 15) prints 25, 26, 27, 28, 29 and returns 32
IterativeUnknown(10, 15) must print the same values and return 32

So the output for this pair is:

parameter line for Unknown
five printed numbers
Unknown return value: 32
parameter line for IterativeUnknown
the same five printed numbers
IterativeUnknown return value: 32

For (10, 10):

both functions hit the base case immediately
neither function prints any intermediate values
both return 1

So only the parameter lines and result lines appear.

For (15, 10):

both functions print 25, 24, 23, 22, 21
both return 0

Putting all three cases together gives the complete expected console output shown in the answer.

This output demonstrates that the iterative version matches the recursive version for all three tests.

Key Takeaways

Matching outputs for the same test data is strong evidence that two function versions are equivalent.
Tracing console output requires attention to both side effects and return values.
Base cases often produce much shorter output than recursive or iterative repeated cases.

Common Mistakes

Forgetting that each function call has its own parameter line in the amended main program.
Omitting the intermediate printed values from one of the functions.
Assuming the iterative function prints nothing because it is not recursive.
Mixing up the labels Unknown and IterativeUnknown in the final output.

Things to Be Careful About

The order of lines must match the execution order exactly.
Unknown return value: appears only after all prints from Unknown() are finished.
IterativeUnknown return value: appears only after all prints from IterativeUnknown() are finished.
For (10, 10), no intermediate values are printed by either function because the base case is reached immediately.

Techniques used

trace the output of both function versions for identical inputscompare recursive and iterative behaviourdetermine exact console output order

The rest of this paper

2 more questions

Q2Programming Paradigms (Procedural and Object-oriented) · File Processing and Exception Handling · Algorithms and Abstract Data Types30M
Q3Programming Paradigms (Procedural and Object-oriented) · Algorithms and Abstract Data Types · Recursion28M

Loading the full paper…

Computer Science 9618/42 — October/November 2021

Answer

Background Concept

Understanding the Question

Approach

Step-by-Step Reasoning

Key Takeaways

Common Mistakes

Things to Be Careful About

Answer

Background Concept

Understanding the Question

Approach

Step-by-Step Reasoning

Key Takeaways

Common Mistakes

Things to Be Careful About

Answer

Background Concept

Understanding the Question

Approach

Step-by-Step Reasoning

Key Takeaways

Common Mistakes

Things to Be Careful About

Answer

Background Concept

Understanding the Question

Approach

Step-by-Step Reasoning

Case 1: X < Y

Case 2: X == Y

Case 3: X > Y

Key Takeaways

Common Mistakes

Things to Be Careful About

Answer

Background Concept

Understanding the Question

Approach

Step-by-Step Reasoning

Key Takeaways

Common Mistakes

Things to Be Careful About

Answer

Background Concept

Understanding the Question

Approach

Step-by-Step Reasoning

Key Takeaways

Common Mistakes

Things to Be Careful About

The rest of this paper

Case 1: `X < Y`

Case 2: `X == Y`

Case 3: `X > Y`