Recursion and Advanced Algorithms - Worksheets, Questions and Revision
9 original exam-style questions - 7 pages of questions with a full mark scheme - free printable PDF.
Recursion and Advanced Algorithms revision guideMore A Level Computer Science practiceMock exams
This topic is chapter 2 of A Level Computer Science Topic Workbook 2 and chapter 10 of A Level Computer Science 10-Minute Tests.
2.8 Recursion and Advanced Algorithms
catalogue = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] (indices 0 to 9)
A recursive binary search function is written as follows.
FUNCTION BinarySearch(list, target, low, high)
IF low > high THEN
RETURN -1
ENDIF
mid <- (low + high) DIV 2
IF list[mid] = target THEN
RETURN mid
ELSE
IF list[mid] < target THEN
RETURN BinarySearch(list, target, mid + 1, high)
ELSE
RETURN BinarySearch(list, target, low, mid - 1)
ENDIF
ENDIF
ENDFUNCTIONA: [B, C]
B: [A, D, E]
C: [A, F]
D: [B]
E: [B, F]
F: [C, E]
A recursive depth-first search (DFS) is implemented as follows.
PROCEDURE DFS(graph, vertex, visited)
visited[vertex] <- TRUE
OUTPUT vertex
FOR EACH neighbour IN graph[vertex]
IF visited[neighbour] = FALSE THEN
CALL DFS(graph, neighbour, visited)
ENDIF
ENDFOR
ENDPROCEDUREFUNCTION Fib(n)
IF n <= 1 THEN
RETURN n
ELSE
RETURN Fib(n - 1) + Fib(n - 2)
ENDIF
ENDFUNCTIONQuestion 1
- (a) function header FUNCTION SumList(list, n) definedM1
- (a) base case IF n = 0 THEN RETURN 0M1
- (a) recursive case makes exactly one further call, SumList(list, n - 1)M1
- (a) recursive case correctly adds the (n-1)th element, e.g. RETURN SumList(list, n - 1) + list[n - 1] caoM1
- (a) Answer:
FUNCTION SumList(list, n) IF n = 0 THEN RETURN 0 ELSE RETURN SumList(list, n - 1) + list[n - 1] ENDIF ENDFUNCTION - (b) O(n) oeB1
- (b) Answer: O(n)
- (c) O(n) oeB1
- (c) because a new stack frame is created for every recursive call, and up to n calls are in progress (not yet returned) at the deepest point of the recursion, before any of them returnB1
- (c) Answer: O(n), because up to n stack frames (one per recursive call) exist at the same time at the deepest point of the recursion, before any calls have returned.
- (d) the iterative version uses O(1) (constant) additional memory rather than O(n), since it does not create a new stack frame for every element, avoiding the risk of a stack overflow error for very large n (oe)B1
- (d) Answer: The iterative version only needs a fixed, small amount of extra memory (O(1)), regardless of the size of the array, because it does not create a new stack frame for every element; this avoids the risk of a stack overflow error that the recursive version could hit for a very large array.
Question 2
- (a) the array must already be sorted (into ascending order, as given) oeB1
- (a) Answer: The array must already be sorted into order.
- (b) call 1: low = 0, high = 9, mid = 4, list[4] = 16B1
- (b) call 1 comparison: 16 < 23, so the next call has low = 5, high = 9B1
- (b) call 2: low = 5, high = 9, mid = 7, list[7] = 45B1
- (b) call 2 comparison: 45 > 23, so the next call has low = 5, high = 6B1
- (b) call 3: low = 5, high = 6, mid = 5, list[5] = 23, matches target caoB1
- (b) Answer: Call 1: low=0, high=9, mid=4, list[4]=16 (16<23, so low<-5). Call 2: low=5, high=9, mid=7, list[7]=45 (45>23, so high<-6). Call 3: low=5, high=6, mid=5, list[5]=23 (match).
- (c) 5 is returned ftB1
- (c) 3 calls in total ftB1
- (c) Answer: 5 is returned (the target 23 is stored at index 5); 3 calls are made in total.
- (d) O(log n) oeB1
- (d) each comparison eliminates half of the remaining elements from consideration, so doubling n only requires one more halving (one more comparison) to reduce the search space down to a single element (oe)B1
- (d) Answer: O(log n). Each comparison halves the number of elements still being searched, so however large the array is, only one extra comparison is needed each time its size doubles, since one more halving is enough to bring it back down to the same remaining search space as before.
Question 3
- (a) divide: the list is recursively split in half until every sub-list contains only one element (oe)B1
- (a) merge: pairs of sorted sub-lists are then repeatedly combined back together, in order, until the whole list is a single sorted list again (oe)B1
- (a) Answer: Divide: the list is recursively split into halves until every sub-list holds just one element. Merge: sorted sub-lists are then repeatedly combined back together in the correct order, until the whole list is fully sorted again.
- (b) [8, 3, 5]B1
- (b) [1, 9, 2]B1
- (b) Answer: [8, 3, 5] and [1, 9, 2]
- (c) merging [3] and [5] gives [3, 5]B1
- (c) merging [8] with [3, 5] gives [3, 5, 8] caoB1
- (c) Answer: Merging [3] and [5] gives [3, 5]. Merging [8] with [3, 5] gives [3, 5, 8].
- (d) [1, 2, 3, 5, 8, 9] caoB1
- (d) O(n log n)B1
- (d) Answer: [1, 2, 3, 5, 8, 9]; worst-case time complexity O(n log n).
- (e) merge sort needs extra (auxiliary) memory, proportional to the size of the list (O(n)), to hold the sub-lists during merging, since it is not an in-place algorithm (oe)B1
- (e) Answer: Merge sort is not in-place: it needs additional memory, proportional to the size of the list, to hold the sub-lists while merging, unlike an in-place algorithm such as insertion sort, which sorts within the original array.
Question 4
- (a) move the top n - 1 disks from source to spare, using destination as the temporary pegB1
- (a) then move the single remaining (largest) disk directly from source to destinationB1
- (a) then move the n - 1 disks from spare to destination, using source as the temporary peg; base case: if n = 0, do nothing (there are no disks to move)B1
- (a) Answer: Move the top n - 1 disks from source to spare (using destination as the temporary peg); move the remaining largest disk from source directly to destination; then move the n - 1 disks from spare to destination (using source as the temporary peg). Base case: if n = 0, there is nothing to move, so the procedure does nothing.
- (b) procedure header PROCEDURE Hanoi(n, source, destination, spare) definedM1
- (b) base case guard, e.g. IF n > 0 THEN (equivalent to stopping when n = 0)M1
- (b) recursive calls in the correct order: CALL Hanoi(n - 1, source, spare, destination) before, and CALL Hanoi(n - 1, spare, destination, source) after, moving the largest diskM1
- (b) correct OUTPUT statement for moving the single disk, placed between the two recursive calls caoM1
- (b) Answer:
PROCEDURE Hanoi(n, source, destination, spare) IF n > 0 THEN CALL Hanoi(n - 1, source, spare, destination) OUTPUT "Move disk ", n, " from ", source, " to ", destination CALL Hanoi(n - 1, spare, destination, source) ENDIF ENDPROCEDURE - (c) formula: 2n - 1B1
- (c) for n = 5: 25 - 1 = 31 caoB1
- (c) Answer: 2n - 1; for n = 5 this gives 25 - 1 = 31 moves.
- (d) O(2n)B1
- (d) because each call to Hanoi(n, ...) makes two further recursive calls, each on n - 1, so the number of calls (and moves) roughly doubles for every extra disk, matching the exponential growth of the 2n - 1 moves formula from part (c) (oe)B1
- (d) Answer: O(2n). Each call to Hanoi(n, ...) makes two further recursive calls on n - 1, so the total number of calls made (and moves output) roughly doubles every time n increases by 1, which is exactly the exponential growth shown by the 2n - 1 moves formula in part (c).
Question 5
- (a) recursive DFS implicitly uses the call stackB1
- (a) an iterative version would need to manage its own explicit stack (a LIFO data structure) oeB1
- (a) Answer: Recursive DFS implicitly uses the call stack. An iterative version would need to manage its own explicit stack (a LIFO data structure) to achieve the same behaviour.
- (b) correctly starts A, B (A's first unvisited neighbour)M1
- (b) correctly continues from B to D (B's first unvisited neighbour, alphabetically before E), before D has to backtrack (D's only neighbour, B, is already visited)M1
- (b) correctly backtracks to B and continues to E, then from E to F (E's only unvisited neighbour)M1
- (b) complete, correct final order: A, B, D, E, F, C caoA1
- (b) Answer: A, B, D, E, F, C
- (c) DFS explores as far as possible down one branch before backtracking to try others, so it may reach a vertex via a long, roundabout route before a shorter route is ever tried, meaning the first path it finds is not necessarily the shortest oneB1
- (c) breadth-first search (BFS) guarantees the shortest path in an unweighted graph, because it explores all vertices at the current distance from the start before moving on to vertices one edge further awayB1
- (c) Answer: DFS commits to exploring one branch as deeply as possible before backtracking, so it can find a long, roundabout path to a vertex before ever trying a shorter one, meaning the path it finds first is not guaranteed to be the shortest. Breadth-first search (BFS) does guarantee the shortest path in an unweighted graph, because it explores every vertex at the current distance from the start before moving on to vertices one edge further away.
Question 6
- (a) correctly places O(1) first and O(2n) lastM1
- (a) correctly places O(log n) second and O(n) thirdM1
- (a) complete, correct order: O(1), O(log n), O(n), O(n log n), O(n2), O(2n) caoA1
- (a) Answer: O(1), O(log n), O(n), O(n log n), O(n2), O(2n)
- (b) recognises that time scales with n2, so the ratio of times equals the ratio of n2 values: (400/100)2M1
- (b) (400/100)2 = 42 = 16M1
- (b) 50 x 16 = 800 milliseconds caoA1
- (b) Answer: 800 milliseconds
- (c) the O(n log n) algorithm would be preferredB1
- (c) because, for large n, n log n grows far more slowly than n2, so the O(n log n) algorithm will complete in significantly less time (and scale much better as n keeps increasing) oeB1
- (c) Answer: The O(n log n) algorithm would be preferred for very large n, because n log n grows far more slowly than n2 as n increases, so it will complete in significantly less time and scale much better for very large inputs.
Question 7
- (a) correctly shows Fib(4) branching into Fib(3) and Fib(2)B1
- (a) correctly expands at least one further level, e.g. Fib(3) branching into Fib(2) and Fib(1), and/or Fib(2) branching into Fib(1) and Fib(0)B1
- (a) value returned: Fib(4) = 3 caoB1
- (a) Answer: Fib(4) calls Fib(3) and Fib(2). Fib(3) calls Fib(2) and Fib(1). Each Fib(2) call calls Fib(1) and Fib(0). Fib(4) returns 3.
- (b) recognises the total number of calls T(n) satisfies T(n) = T(n-1) + T(n-2) + 1, with T(0) = T(1) = 1 (or builds the call tree directly)M1
- (b) 15 total calls caoA1
- (b) 5 calls to Fib(1) caoA1
- (b) Answer: 15 calls are made in total, of which 5 are calls to Fib(1).
- (c) without memoisation, the same values (e.g. Fib(2), Fib(1)) are recalculated repeatedly by many different branches of the call tree, and the number of calls roughly doubles each time n increases by 1, giving O(2n) timeB1
- (c) memoisation stores each Fib(k) value the first time it is calculated (e.g. in an array memo), and checks this array before making any recursive calls for that valueB1
- (c) so every distinct value from Fib(0) to Fib(n) is calculated only once, reducing the time complexity to O(n)B1
- (c) Answer: The naive version recalculates the same Fibonacci values many times (e.g. Fib(2) is calculated separately inside the call trees for both Fib(4) and Fib(3)), and the total number of calls roughly doubles for each increase in n, giving exponential, O(2n), time. Memoisation stores each Fib(k) result the first time it is worked out, in a lookup array, and checks this array before recalculating; this means every distinct value from Fib(0) up to Fib(n) is only ever calculated once, reducing the time complexity to O(n).
- (d) base case IF n ≤ 1 THEN RETURN nM1
- (d) checks whether the value is already stored, e.g. IF memo[n] <> -1 THEN RETURN memo[n]M1
- (d) calculates and stores the new value before returning it, e.g. memo[n] <- FibMemo(n - 1, memo) + FibMemo(n - 2, memo) followed by RETURN memo[n] caoM1
- (d) Answer:
FUNCTION FibMemo(n, memo) IF n <= 1 THEN RETURN n ENDIF IF memo[n] <> -1 THEN RETURN memo[n] ENDIF memo[n] <- FibMemo(n - 1, memo) + FibMemo(n - 2, memo) RETURN memo[n] ENDFUNCTION
Question 8
- (a) 3B1
- (a) Answer: 3
- (b) identifies which elements are less than the pivot (2 and 1) and groups them before itM1
- (b) identifies which elements are greater than or equal to the pivot (5, 8 and 9) and groups them after itM1
- (b) [2, 1, 3, 5, 9, 8] cao (or an equivalent list showing 2 and 1 before the correctly-placed pivot 3, and 5, 9, 8, in any order, after it)A1
- (b) Answer: [2, 1, 3, 5, 9, 8]
- (c) [2, 1] ftB1
- (c) [5, 9, 8] ftB1
- (c) Answer: [2, 1] and [5, 9, 8]
- (d) best case: O(n log n)B1
- (d) worst case: O(n2)B1
- (d) the worst case occurs when the list is already fully sorted (or fully reverse-sorted), since then the pivot (the last element) is always the largest (or smallest) of the remaining elements, giving a maximally unbalanced partition (one sub-list of size 0 and one of size n - 1) every timeB1
- (d) Answer: Best case: O(n log n). Worst case: O(n2), which occurs when the list is already sorted (or reverse-sorted), since the last element is then always the largest (or smallest) remaining value, giving one empty sub-list and one sub-list of size n - 1 at every partition step.
Question 9
- Level 3 A detailed, well-balanced discussion covers multiple relevant points on both sides (advantages and disadvantages of recursion), using accurate technical terminology (e.g. call stack, stack frame, space complexity) and at least one well-chosen example problem to illustrate when each approach is preferred. The answer is coherently structured and reaches a supported overall judgement.5-6
- Level 2 A reasonable discussion of several relevant points is given, covering both recursion and iteration to some extent, with generally correct terminology, but development, examples or balance between the two approaches may be limited.3-4
- Level 1 Basic or list-like statements are made about recursion and/or iteration, with limited justification, little or no use of relevant technical terminology, and little reference to specific examples.1-2
- Level 0 No creditable content.0
- Indicative content:
- Recursive solutions can be more readable and concise than iterative ones, especially for problems that are themselves naturally recursive in structure, such as traversing a tree, exploring a graph, or divide-and-conquer algorithms like merge sort and quicksort.
- Each recursive call adds a new stack frame to the call stack, storing that call's local variables, parameters and return address, so a recursive algorithm's space complexity is often O(n) (proportional to its depth) rather than the O(1) that a simple iterative loop typically needs.
- If the recursion depth becomes too large (e.g. an insufficient or missing base case, or simply a very large input), the call stack can run out of memory, causing a stack overflow error and crashing the program; an equivalent iterative loop has no such risk.
- Making a function call has some processing overhead (pushing and popping stack frames) compared with a single loop iteration, so a well-written iterative version is often somewhat faster in practice for simple, repetitive tasks such as summing a list.
- Some problems, such as depth-first search, backtracking algorithms, or processing a tree with an unpredictable number of levels, are considerably harder to write iteratively (often requiring the programmer to manage their own explicit stack), so recursion can reduce code complexity and the risk of bugs despite its performance and memory cost.
- A balanced conclusion typically judges that recursion is preferable when it closely matches the natural structure of the problem (e.g. tree/graph traversal, divide-and-conquer), while iteration is preferable for simple, repetitive tasks over large inputs, or wherever memory use or guaranteed performance is a priority.
Mark your answers
Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.