Skip to the worksheet
Revision Library
Choose a subject

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.

This topic is chapter 2 of A Level Computer Science Topic Workbook 2 and chapter 10 of A Level Computer Science 10-Minute Tests.

Revision Library
revisionlibrary.co.uk
A-Level · AQA

2.8 Recursion and Advanced Algorithms

AQA 7517 · Calculators not allowed · about 95 minutes
Total Marks
Name: _______________________________    Date: ____ / ____ / ______
Answer ALL questions. Show all your working.
1
A programmer named Aisha is writing a recursive function to add up the first n elements of an array called list (indexed from 0).
(a)Using AQA pseudocode conventions, write a recursive function SumList(list, n) that returns the sum of the first n elements of list (i.e. list[0] up to list[n-1]). Your function should return 0 if n = 0.(4)
(b)State the time complexity of SumList in Big O notation, in terms of n.(1)
(c)State the space complexity of SumList in Big O notation, giving a reason related to the call stack.(2)
(d)An iterative version of SumList uses a single WHILE loop and one accumulator variable instead of recursion. State one advantage of the iterative version over the recursive version for a very large array.(1)
(Total for Question 1 is 8 marks)
2
An array called catalogue, indexed from 0, holds 10 sorted reference numbers:

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
ENDFUNCTION
(a)State one precondition that must hold for the array catalogue before binary search can be used on it correctly.(1)
(b)Complete a trace table for the call BinarySearch(catalogue, 23, 0, 9), showing the values of low, high, mid and list[mid] for each recursive call made, until the target is found.(5)
(c)State the value returned by the original call, and the total number of recursive calls made (including the first call).(2)
(d)State the time complexity of binary search in Big O notation, and explain why doubling the number of elements in a sorted array only adds, at most, one extra comparison to a binary search of it.(2)
(Total for Question 2 is 10 marks)
3
Merge sort is a recursive, divide-and-conquer sorting algorithm. It is applied to the list [8, 3, 5, 1, 9, 2].
(a)State the two main phases of the merge sort algorithm.(2)
(b)State the two sub-lists produced when [8, 3, 5, 1, 9, 2] is first split in half.(2)
(c)The sub-list [8, 3, 5] is recursively split down into single-element lists ([8], [3] and [5]) and then merged back together. State the result of merging [3] and [5] first, and then state the result of merging [8] with that result.(2)
(d)By the same process, [1, 9, 2] merges down to [1, 2, 9]. State the fully sorted list produced when [3, 5, 8] and [1, 2, 9] are finally merged together, and state the worst-case time complexity of merge sort in Big O notation.(2)
(e)State one disadvantage of merge sort compared with an in-place sorting algorithm such as insertion sort.(1)
(Total for Question 3 is 9 marks)
4
In the Towers of Hanoi puzzle, n disks of different sizes are stacked on a source peg, and must all be moved to a destination peg, using a third, spare peg, following two rules: only one disk may be moved at a time, and a larger disk may never be placed on top of a smaller one.
(a)State the recursive rule used to move n disks (n > 0) from a source peg to a destination peg, using a spare peg, and state the base case for n = 0.(3)
(b)Using AQA pseudocode conventions, write a recursive procedure Hanoi(n, source, destination, spare) that outputs the sequence of moves needed.(4)
(c)State the formula for the minimum number of moves needed to solve the puzzle with n disks, and use it to calculate the number of moves needed for 5 disks.(2)
(d)State the time complexity of the Hanoi procedure in Big O notation, in terms of n, and explain why.(2)
(Total for Question 4 is 11 marks)
5
A graph is stored as an adjacency list, where each vertex lists its directly connected neighbours in alphabetical order:

A: [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
ENDPROCEDURE
(a)State the data structure that recursive DFS implicitly uses to keep track of which vertices to return to, and name the equivalent explicit data structure that an iterative version of DFS would need to manage this itself.(2)
(b)Using the pseudocode and the adjacency list given, and assuming neighbours are always considered in the alphabetical order shown, state the order in which the vertices are visited (output) when CALL DFS(graph, A, visited) is made, with every vertex initially unvisited.(4)
(c)Explain why DFS is not guaranteed to find the shortest path (fewest edges) between two vertices in an unweighted graph, and name an alternative graph traversal algorithm that would guarantee this.(2)
(Total for Question 5 is 8 marks)
6
Time complexities are often compared using Big O notation to describe how an algorithm's running time grows as the size of its input, n, increases.
(a)State the following time complexities in order, from the most efficient (slowest growing) to the least efficient (fastest growing), as n becomes very large: O(n), O(log n), O(n2), O(1), O(n log n), O(2n).(3)
(b)An algorithm has time complexity O(n2). When n = 100, it takes approximately 50 milliseconds to run on a particular computer. Assuming the same constant of proportionality, calculate an estimate for how long the same algorithm would take to run on the same computer when n = 400. Show your working.(3)
(c)A different algorithm, solving the same underlying problem, has time complexity O(n log n) instead. State, with a reason, which of the two algorithms (the O(n2) one from part (b), or this O(n log n) one) would be preferred for very large values of n.(2)
(Total for Question 6 is 8 marks)
7
The following recursive AQA pseudocode function calculates the nth Fibonacci number, where Fib(0) = 0, Fib(1) = 1, and Fib(n) = Fib(n-1) + Fib(n-2) for n ≥ 2.
FUNCTION Fib(n)
   IF n <= 1 THEN
      RETURN n
   ELSE
      RETURN Fib(n - 1) + Fib(n - 2)
   ENDIF
ENDFUNCTION
(a)Describe the tree of recursive calls made when evaluating Fib(4) (state which calls each call makes), and state the value returned.(3)
(b)For the larger call Fib(5), state the total number of function calls made in total (including the initial call to Fib(5) itself), and state how many of these calls are calls to the base case Fib(1).(3)
(c)Explain why the time complexity of Fib(n), as written above, is exponential, O(2n), and explain how storing previously computed results in a lookup array (memoisation) improves this.(3)
(d)Using AQA pseudocode conventions, write a memoised version FibMemo(n, memo), where memo is an array, indexed from 0, with every element initially set to -1 to indicate that value has not yet been calculated.(3)
(Total for Question 7 is 12 marks)
8
The list [5, 2, 8, 1, 9, 3] is sorted using quicksort, using the Lomuto partition scheme with the last element of the (sub-)list always chosen as the pivot.
(a)State the pivot used for the first partition step.(1)
(b)Show the list after the first partition step is complete (elements less than the pivot moved before it, elements greater than or equal to the pivot moved after it, and the pivot placed in its final, correctly sorted position).(3)
(c)State the two sub-lists that quicksort will now be called on recursively.(2)
(d)State the best-case and worst-case time complexity of quicksort in Big O notation, and describe the input list that causes the worst case when the pivot is always chosen as the last element.(3)
(Total for Question 8 is 9 marks)
9
Discuss the advantages and disadvantages of solving a problem using a recursive algorithm rather than an equivalent iterative algorithm. Your answer should consider readability, memory use and performance, and should refer to specific examples of problems for which one approach is generally preferred over the other.
(Total for Question 9 is 6 marks)
Mark scheme · 2.8 Recursion and Advanced Algorithms

Question 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.

Question 1

8 marks
Did your answer earn the marks?

Question 2

10 marks
Did your answer earn the marks?

Question 3

9 marks
Did your answer earn the marks?

Question 4

11 marks
Did your answer earn the marks?

Question 5

8 marks
Did your answer earn the marks?

Question 6

8 marks
Did your answer earn the marks?

Question 7

12 marks
Did your answer earn the marks?

Question 8

9 marks
Did your answer earn the marks?

Question 9

6 marks
Did your answer earn the marks?
Mark my answers

Worksheets are written for Revision Library and come with a full mark scheme; a few English packs quote an out-of-copyright text, and name it on the page. Exam board names and specification codes say which qualification a pack suits: we are not affiliated with, endorsed by or approved by any exam board, and no past-paper question is reproduced here. Rights queries: hello@revisionlibrary.co.uk