Revision Library

revisionlibrary.co.uk

A-Level · AQA

A1.10 Recursion and Advanced Algorithms

AQA 7517 · Calculators not allowed · about 130 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

A programmer writes the following recursive AQA pseudocode function to calculate the factorial of a non-negative integer n (where n! = n x (n-1) x (n-2) x ... x 1, and 0! is defined as 1).

FUNCTION Factorial(n)
   IF n = 0 THEN
      RETURN 1
   ELSE
      RETURN n * Factorial(n - 1)
   ENDIF
ENDFUNCTION

(a)State the base case of the function Factorial(n).(1)

(b)Complete a trace table showing the value of n passed to each recursive call made when evaluating Factorial(5), and the value each call returns, from the first call (n = 5) to the last.(5)

(c)State the value returned by the original call Factorial(5).(1)

(d)The function is instead called with a negative argument, Factorial(-3). Explain, with reference to the base case and the call stack, what would happen, and why this is a general risk when writing recursive functions.(3)

(Total for Question 1 is 10 marks)

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 2 is 8 marks)

A games programmer called Rhys is writing a recursive backtracking function to find a path through a maze, represented as a 2D array grid, where grid[row][col] = 0 means an open cell and grid[row][col] = 1 means a wall. The array visited keeps track of cells already tried during the current search, and target holds the row and column of the exit cell. Two lines of the pseudocode, labelled ____(i)____ and ____(ii)____, have been removed.

FUNCTION SolveMaze(grid, row, col, target, visited)
   IF row < 0 OR row >= LEN(grid) OR col < 0 OR col >= LEN(grid[0]) THEN
      RETURN FALSE
   ENDIF
   IF grid[row][col] = 1 OR visited[row][col] = TRUE THEN
      RETURN FALSE
   ENDIF
   IF row = target[0] AND col = target[1] THEN
      RETURN TRUE
   ENDIF
   ____(i)____
   IF SolveMaze(grid, row + 1, col, target, visited) = TRUE THEN
      RETURN TRUE
   ENDIF
   IF SolveMaze(grid, row - 1, col, target, visited) = TRUE THEN
      RETURN TRUE
   ENDIF
   IF SolveMaze(grid, row, col + 1, target, visited) = TRUE THEN
      RETURN TRUE
   ENDIF
   IF SolveMaze(grid, row, col - 1, target, visited) = TRUE THEN
      RETURN TRUE
   ENDIF
   ____(ii)____
   RETURN FALSE
ENDFUNCTION

(a)State the missing pseudocode for the lines labelled ____(i)____ and ____(ii)____.(2)

(b)State the purpose of the visited array in this algorithm.(1)

(c)Explain why line ____(ii)____ (resetting visited[row][col] back to FALSE) is essential for the algorithm to correctly explore every possible path through the maze, rather than just the first path it happens to try.(2)

(d)State what the original call to SolveMaze returns if no path exists between the start cell and the target, and explain, with reference to the recursive calls, how the algorithm reaches this result.(3)

(Total for Question 3 is 8 marks)

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(2ⁿ), 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 4 is 12 marks)

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 5 is 10 marks)

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 6 is 9 marks)

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 7 is 9 marks)

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 8 is 11 marks)

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)

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 10 is 8 marks)

A binary search tree stores nodes with a value, a left child pointer and a right child pointer (NULL if there is no child). The tree used in this question has the following structure:

Root: 50
50's left child: 30, 50's right child: 70
30's left child: 20, 30's right child: 40
70's left child: 60, 70's right child: 80
(20, 40, 60 and 80 are all leaves, with no children)

The following recursive procedure is defined.

PROCEDURE InOrder(node)
   IF node <> NULL THEN
      CALL InOrder(node.left)
      OUTPUT node.value
      CALL InOrder(node.right)
   ENDIF
ENDPROCEDURE

(a)State the standard name given to the tree traversal implemented by this pseudocode, in terms of the order in which a node's left subtree, the node itself, and its right subtree are processed.(1)

(b)State the full sequence of values output when CALL InOrder(root) is made on the tree described above.(1)

(c)Complete a trace table showing, in order, the node value passed to each call InOrder(node) made on a node that actually holds a value (i.e. exclude any call made where node = NULL, which returns immediately), listing the order in which these calls are first entered.(4)

(d)The order of calls found in part (c) is identical to a different, standard tree traversal order. Identify this traversal, and justify your answer by referring to when a node's own value would be processed relative to its child subtrees in that traversal.(2)

(Total for Question 11 is 8 marks)

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(n²), O(1), O(n log n), O(2ⁿ).(3)

(b)An algorithm has time complexity O(n²). 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(n²) one from part (b), or this O(n log n) one) would be preferred for very large values of n.(2)

(Total for Question 12 is 8 marks)

Mark scheme · A1.10 Recursion and Advanced Algorithms

Question 1

(a) B1 n = 0 (the function returns 1 immediately without a further recursive call) oe
(a) Answer: The base case is n = 0, where the function returns 1 without making any further recursive call.
(b) B1 call with n = 1 returns 1 (the base case)
(b) B1 call with n = 2 returns 2
(b) B1 call with n = 3 returns 6
(b) B1 call with n = 4 returns 24
(b) B1 call with n = 5 returns 120 cao
(b) Answer:
n returns
1 1
2 2
3 6
4 24
5 120
(c) B1 120 cao ft from (b)
(c) Answer: 120
(d) B1 the base case n = 0 is never reached, because each recursive call passes n - 1, so the sequence of values (-3, -4, -5, ...) decreases without ever equalling 0
(d) B1 the function therefore keeps calling itself indefinitely (infinite recursion), with each call adding a new frame to the call stack, but no call ever returns
(d) B1 eventually the call stack runs out of available memory, causing a stack overflow error and the program to crash; this shows why every recursive function needs a base case that is guaranteed to be reached for all inputs it might realistically be called with
(d) Answer: Because the base case only checks for n = 0, and each call passes n - 1, calling Factorial(-3) produces the sequence -3, -4, -5, ... which never equals 0. The base case is never reached, so the function recurses indefinitely, adding a new stack frame on every call without any of them returning, until the call stack runs out of memory and the program crashes with a stack overflow error. This illustrates the general risk that a recursive function's base case must be reached for every input it might realistically be called with.

n	returns
1	1
2	2
3	6
4	24
5	120

Question 2

(a) M1 function header FUNCTION SumList(list, n) defined
(a) M1 base case IF n = 0 THEN RETURN 0
(a) M1 recursive case makes exactly one further call, SumList(list, n - 1)
(a) M1 recursive case correctly adds the (n-1)th element, e.g. RETURN SumList(list, n - 1) + list[n - 1] cao

(a) Answer:

FUNCTION SumList(list, n)
   IF n = 0 THEN
      RETURN 0
   ELSE
      RETURN SumList(list, n - 1) + list[n - 1]
   ENDIF
ENDFUNCTION

(b) B1 O(n) oe
(b) Answer: O(n)
(c) B1 O(n) oe
(c) B1 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 return
(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) B1 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)
(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 3

(a) B1 (i): visited[row][col] <- TRUE
(a) B1 (ii): visited[row][col] <- FALSE
(a) Answer:(i) visited[row][col] <- TRUE
(ii) visited[row][col] <- FALSE
(b) B1 it records which cells are currently part of the path being explored, so the algorithm does not revisit a cell already being tried and get stuck moving back and forth between the same cells forever (oe)
(b) Answer: The visited array keeps track of which cells are already part of the path currently being explored, so the algorithm does not try to move back into a cell it is already using and end up looping between the same cells indefinitely.
(c) B1 without this line, once a cell had been marked visited it would remain marked as such even after the recursive call exploring onward from it had returned FALSE (a dead end)
(c) B1 so if a different, still-active call later tried to pass back through that same cell as part of an alternative route to the target, it would incorrectly be treated as unavailable, and a genuine solution path could be missed
(c) Answer: Without resetting visited[row][col] back to FALSE, a cell would stay marked as visited even after the branch of the search starting from it had failed (returned FALSE). If a different recursive call later needed to pass back through that same cell to reach the target by another route, it would wrongly be blocked, so the algorithm could fail to find a path that actually exists.
(d) B1 FALSE is returned
(d) B1 every recursive call from every reachable cell eventually returns FALSE, either immediately (hitting a wall, the maze boundary, or an already-visited cell) or because all four of its own recursive calls returned FALSE
(d) B1 this propagates back up through every call in the chain (each one in turn finding none of its own four recursive calls returned TRUE), all the way back to the original call, which therefore also returns FALSE
(d) Answer: The original call returns FALSE. Every recursive call made during the search eventually returns FALSE, either straight away (because it hits a wall, the edge of the maze, or a cell already visited on this path) or because it tried all four directions and each of those calls also returned FALSE. Since no call anywhere in the search ever finds a path to the target, this FALSE result passes back up through every level of recursion until the original call itself returns FALSE.

Question 4

(a) B1 correctly shows Fib(4) branching into Fib(3) and Fib(2)
(a) B1 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)
(a) B1 value returned: Fib(4) = 3 cao
(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) M1 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)
(b) A1 15 total calls cao
(b) A1 5 calls to Fib(1) cao
(b) Answer: 15 calls are made in total, of which 5 are calls to Fib(1).
(c) B1 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(2ⁿ) time
(c) B1 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 value
(c) B1 so every distinct value from Fib(0) to Fib(n) is calculated only once, reducing the time complexity to O(n)
(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(2ⁿ), 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) M1 base case IF n ≤ 1 THEN RETURN n
(d) M1 checks whether the value is already stored, e.g. IF memo[n] <> -1 THEN RETURN memo[n]
(d) M1 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] cao

(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 5

(a) B1 the array must already be sorted (into ascending order, as given) oe
(a) Answer: The array must already be sorted into order.
(b) B1 call 1: low = 0, high = 9, mid = 4, list[4] = 16
(b) B1 call 1 comparison: 16 < 23, so the next call has low = 5, high = 9
(b) B1 call 2: low = 5, high = 9, mid = 7, list[7] = 45
(b) B1 call 2 comparison: 45 > 23, so the next call has low = 5, high = 6
(b) B1 call 3: low = 5, high = 6, mid = 5, list[5] = 23, matches target cao
(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) B1 5 is returned ft
(c) B1 3 calls in total ft
(c) Answer: 5 is returned (the target 23 is stored at index 5); 3 calls are made in total.
(d) B1 O(log n) oe
(d) B1 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)
(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 6

(a) B1 divide: the list is recursively split in half until every sub-list contains only one element (oe)
(a) B1 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)
(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) B1 [8, 3, 5]
(b) B1 [1, 9, 2]
(b) Answer: [8, 3, 5] and [1, 9, 2]
(c) B1 merging [3] and [5] gives [3, 5]
(c) B1 merging [8] with [3, 5] gives [3, 5, 8] cao
(c) Answer: Merging [3] and [5] gives [3, 5]. Merging [8] with [3, 5] gives [3, 5, 8].
(d) B1 [1, 2, 3, 5, 8, 9] cao
(d) B1 O(n log n)
(d) Answer: [1, 2, 3, 5, 8, 9]; worst-case time complexity O(n log n).
(e) B1 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)
(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 7

(a) B1 3
(a) Answer: 3
(b) M1 identifies which elements are less than the pivot (2 and 1) and groups them before it
(b) M1 identifies which elements are greater than or equal to the pivot (5, 8 and 9) and groups them after it
(b) A1 [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)
(b) Answer: [2, 1, 3, 5, 9, 8]
(c) B1 [2, 1] ft
(c) B1 [5, 9, 8] ft
(c) Answer: [2, 1] and [5, 9, 8]
(d) B1 best case: O(n log n)
(d) B1 worst case: O(n²)
(d) B1 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 time
(d) Answer: Best case: O(n log n). Worst case: O(n²), 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 8

(a) B1 move the top n - 1 disks from source to spare, using destination as the temporary peg
(a) B1 then move the single remaining (largest) disk directly from source to destination
(a) B1 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)
(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) M1 procedure header PROCEDURE Hanoi(n, source, destination, spare) defined
(b) M1 base case guard, e.g. IF n > 0 THEN (equivalent to stopping when n = 0)
(b) M1 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 disk
(b) M1 correct OUTPUT statement for moving the single disk, placed between the two recursive calls cao

(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) B1 formula: 2ⁿ - 1
(c) B1 for n = 5: 2⁵ - 1 = 31 cao
(c) Answer: 2ⁿ - 1; for n = 5 this gives 2⁵ - 1 = 31 moves.
(d) B1 O(2ⁿ)
(d) B1 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 2ⁿ - 1 moves formula from part (c) (oe)
(d) Answer: O(2ⁿ). 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 2ⁿ - 1 moves formula in part (c).

Question 9

Level 3 (5-6): 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.
Level 2 (3-4): 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.
Level 1 (1-2): 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.
Level 0 (0): No creditable content.
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.

Question 10

(a) B1 recursive DFS implicitly uses the call stack
(a) B1 an iterative version would need to manage its own explicit stack (a LIFO data structure) oe
(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) M1 correctly starts A, B (A's first unvisited neighbour)
(b) M1 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)
(b) M1 correctly backtracks to B and continues to E, then from E to F (E's only unvisited neighbour)
(b) A1 complete, correct final order: A, B, D, E, F, C cao
(b) Answer: A, B, D, E, F, C
(c) B1 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 one
(c) B1 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 away
(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 11

(a) B1 in-order traversal (left subtree, then the node itself, then right subtree) oe
(a) Answer: In-order traversal (left subtree, then the node, then right subtree).
(b) B1 20, 30, 40, 50, 60, 70, 80 cao
(b) Answer: 20, 30, 40, 50, 60, 70, 80
(c) B1 50, 30, 20 correct as the first three calls entered (descending down the left spine)
(c) B1 40 correctly placed as the fourth call entered (after backtracking from 20, following node 30's right pointer)
(c) B1 70, 60 correctly placed as the fifth and sixth calls entered (after backtracking all the way to 50, then following its right pointer, then 70's left pointer)
(c) A1 complete, correct full order: 50, 30, 20, 40, 70, 60, 80 cao
(c) Answer: 50, 30, 20, 40, 70, 60, 80
(d) B1 pre-order traversal
(d) B1 pre-order processes a node's own value before (immediately on entering, ahead of) recursing into its left and right subtrees, i.e. "node, then left, then right", which is exactly the order that calls are entered in part (c), regardless of when in-order's own OUTPUT statement actually runs
(d) Answer: Pre-order traversal. Pre-order visits (processes) a node before recursing into either of its subtrees, "node, left, right", and since every traversal, including in-order, always enters InOrder(node.left) as its very first action inside a call, the order in which calls are first entered on real nodes always matches the node-first order of a pre-order traversal, whichever traversal's own OUTPUT statement is actually being run.

Question 12

(a) M1 correctly places O(1) first and O(2ⁿ) last
(a) M1 correctly places O(log n) second and O(n) third
(a) A1 complete, correct order: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) cao
(a) Answer: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)
(b) M1 recognises that time scales with n², so the ratio of times equals the ratio of n² values: (400/100)²
(b) M1 (400/100)² = 4² = 16
(b) A1 50 x 16 = 800 milliseconds cao
(b) Answer: 800 milliseconds
(c) B1 the O(n log n) algorithm would be preferred
(c) B1 because, for large n, n log n grows far more slowly than n², so the O(n log n) algorithm will complete in significantly less time (and scale much better as n keeps increasing) oe
(c) Answer: The O(n log n) algorithm would be preferred for very large n, because n log n grows far more slowly than n² as n increases, so it will complete in significantly less time and scale much better for very large inputs.

Recursion and Advanced Algorithms - Worksheets, Questions and Revision