Home · A-Level Computer Science 9618 · Computational thinking and problem-solving · Recursion and the call stack · Practice
A2 · Practice questions · Recursion and the call stack

Base case first.

Six original Cambridge-style questions on recursion: features, traces, pseudocode and the call stack.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.
Keep these straight

Down, then up.

01
Explain
[3 marks]

State the three essential features of a recursive subroutine.

  • It calls itself (is defined in terms of itself). ✓
  • It has a base case / stopping condition that returns a value without a recursive call. ✓
  • It has a general case that calls itself with arguments that move towards the base case. ✓
02
Trace
[4 marks]

Trace the function below for DigitSum(4721), showing each call, the value it waits for and the value it returns.

FUNCTION DigitSum(n : INTEGER) RETURNS INTEGER
    IF n < 10 THEN
        RETURN n
    ELSE
        RETURN (n MOD 10) + DigitSum(n DIV 10)
    ENDIF
ENDFUNCTION
  • DigitSum(4721) waits for 1 + DigitSum(472); DigitSum(472) waits for 2 + DigitSum(47). ✓
  • DigitSum(47) waits for 7 + DigitSum(4); DigitSum(4) is the base case and returns 4. ✓
  • Unwinding: DigitSum(47) returns 11, DigitSum(472) returns 13. ✓
  • DigitSum(4721) returns 14. ✓
03
Write
[6 marks]

Data : ARRAY[1:100] OF INTEGER is a global array in ascending order. Write pseudocode for a recursive function RBinarySearch(Target : INTEGER, Low : INTEGER, High : INTEGER) RETURNS INTEGER that returns the index of Target, or −1 if it is not present. It is first called as RBinarySearch(Target, 1, 100).

  • Base case: IF Low > High THEN RETURN -1. ✓
  • Mid ← (Low + High) DIV 2. ✓
  • If Data[Mid] = Target, RETURN Mid (second base case). ✓
  • If Data[Mid] < Target, RETURN RBinarySearch(Target, Mid + 1, High). ✓
  • Otherwise RETURN RBinarySearch(Target, Low, Mid - 1). ✓
  • Correct function header, local Mid declared, matching ENDIF / ENDFUNCTION. ✓
04
Trace
[3 marks]

The array in the binary search lesson holds 3, 8, 12, 17, 21, 26, 30, 34, 39, 42, 47, 51, 58, 63, 70 in elements 1 to 15. For your function in the previous question (adapted to this array), state the arguments of every call made by RBinarySearch(9, 1, 15) and the value finally returned.

  • (9, 1, 15): Mid 8, 34 > 9; then (9, 1, 7): Mid 4, 17 > 9. ✓
  • (9, 1, 3): Mid 2, 8 < 9; then (9, 3, 3): Mid 3, 12 > 9; then (9, 3, 2). ✓
  • Low > High in the fifth call, so −1 is returned and passed back up through every call. ✓
05
Explain
[4 marks]

Explain how a compiler handles a recursive call, and why recursion can cause a run-time error.

  • Each call pushes a stack frame onto the call stack. ✓
  • The frame holds the return address, the parameters and the local variables for that call. ✓
  • When a call ends its frame is popped, the return value is passed back and execution continues at the return address (unwinding). ✓
  • If the recursion is too deep or never reaches a base case, the stack runs out of memory: stack overflow. ✓
06
Analysis
[3 marks]

A student writes a recursive function to add up the 1 000 000 values in an array, one element per call. Evaluate this design.

  • It works in principle: base case at the end of the array, general case adds one element to the sum of the rest. ✓
  • But it would need about 1 000 000 stack frames held at once (O(n) space), which is likely to cause a stack overflow, and each call adds time overhead. ✓
  • A simple loop is O(1) space and clearer for this problem, so iteration is the better choice. ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.