Question bank › A-level Computer Science › Fundamentals of programming

Subroutines, parameters, stack frames and recursion

Answer on paper first, then reveal the mark scheme one mark at a time.

1Standard5 marks

The recursive function F is shown below.

FUNCTION F(a, b)
   IF b = 0 THEN
      RETURN a
   ELSE
      RETURN F(b, a MOD b)
   ENDIF
ENDFUNCTION

(a) State the value returned by the call F(84, 36). [1]

(b) State how many times F is called in total, including the original call, when F(84, 36) is executed. [1]

(d) Identify the base case in F and explain why a recursive subroutine must have a base case. [2]

(a) 12(1)
(b) 3 (calls F(84, 36), F(36, 12), F(12, 0))(1)
(c) The highest common factor / greatest common divisor of a and b; accept HCF / GCD; NE 'a factor of a and b'(1)
(d) Base case: when b = 0 (the function returns a without calling itself); accept IF b = 0 THEN RETURN a(1)
(d) Without a base case the subroutine would keep calling itself and never return / terminate; each call adds a stack frame, so eventually the stack overflows / runs out of memory (and the program crashes); accept: the base case is the stopping condition that allows the calls to unwind and return values(1)
Answer: (a) 12 (b) 3 (c) The HCF/GCD of a and b (d) Base case is b = 0 (return a); without one the function keeps calling itself, never returns, and stack frames build up until the stack overflows.
Examiner tip: In (d) say what would actually happen without a base case (endless calls, stack frames building up until stack overflow) rather than just 'it loops forever'.

2Hard4 marks

Consider the Python program below.

def change(x, items):
    x = x + 1
    items.append(x)

a = 5
b = [1]
change(a, b)
print(a, b)

(a) State the output of the program. [2]

(b) Explain why the value of a and the contents of b are affected differently by the call to change. [2]

(a) 5 (a is unchanged)(1)
(a) [1, 6] (b now contains 6)(1)
(b) x is a local variable that receives the value of a; x = x + 1 only changes the local x (integers are immutable, so x now refers to a new value 6), and a in the main program stays 5; accept: a is (effectively) passed by value / a copy of its value is passed, so changing x does not change a(1)
(b) items refers to the same list object as b (a reference to the list is passed, so changes made through items are seen through b); append changes that list in place, so b becomes [1, 6]; accept: b is (effectively) passed by reference so the change made inside the subroutine affects b(1)
Answer: (a) 5 [1, 6] (b) x is effectively a local copy of a's value; items references the same mutable list as b, so append changes b.
Examiner tip: In Python both arguments pass a reference to an object: say what happens to each – x = x + 1 makes the local x refer to a new integer (a is unchanged), while append changes the shared list in place (so b changes).

Book a free 30-minute session on WhatsApp and we'll find exactly which step is costing you the marks. Or build a timed paper on it.