Recursion and quicksort (HL) – IB Computer Science exam questions with mark scheme

1HardHL only5 marks

Consider the recursive function below.

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

(a) State the base case. [1]

(b) Show the sequence of calls made by digit_sum(4729). [1]

(d) State what would happen if the base case were removed. [1]

(a) n < 10 (a single digit is returned unchanged)(1)
(b) digit_sum(4729) → digit_sum(472) → digit_sum(47) → digit_sum(4)(1)
(c) digit_sum(4) returns 4; digit_sum(47) returns 7 + 4 = 11; digit_sum(472) returns 2 + 11 = 13(1)
digit_sum(4729) returns 9 + 13 = 22 (final result 22)(1)
(d) Infinite recursion: the function keeps calling itself (n // 10 reaches 0 and digit_sum(0) calls digit_sum(0) for ever), so it never terminates / the call stack overflows and a RecursionError is raised (accept any one of: infinite recursion, never stops, stack overflow, RecursionError)(1)
Answer: (a) n < 10 (b) 4729, 472, 47, 4 (c) 4, 11, 13, 22 (d) RecursionError (stack overflow)
Examiner tip: Show the value returned at each level as the recursion unwinds, not only the final 22; in (d) say the recursion never stops (stack overflow), not just 'it breaks'.

2CoreHL only4 marks

A games studio uses recursive functions in several parts of its software.

(a) Define the term recursion. [1]

(b) Outline the purpose of a base case in a recursive function. [1]

(a) A function/subroutine/method that calls itself (with a smaller or simpler version of the problem) (allow: solving a problem by defining it in terms of a smaller instance of itself; do not accept 'a loop that repeats')(1)
(b) It is the condition under which the function returns a value without calling itself again, so the recursion stops / terminates (and the calls begin to unwind) (accept: prevents infinite recursion / stack overflow)(1)
(c) Any one from: quicksort (or other recursive sorting, e.g. merge sort); drawing fractals (e.g. Koch snowflake, fractal tree, Sierpinski triangle); traversing a binary tree (in-order / pre-order / post-order); recursive binary search; Towers of Hanoi; searching a folder/directory structure(1)
Second, different application from the list in the previous point (accept quicksort and merge sort as two separate applications; do not accept factorial; ignore vague answers such as 'loops' or 'maths')(1)
Answer: (a) A function that calls itself (b) Stops the recursion: returns without a further call (c) e.g. quicksort; drawing fractals; binary-tree traversal
Examiner tip: In (b) say the base case returns without making another recursive call; 'it is the first case' or 'it is the simplest' alone does not earn the mark.

3CoreHL only4 marks

Consider the following recursive procedure.

def pattern(n):
    if n == 0:
        print("*")
        return
    print(n)
    pattern(n - 1)
    print(n * 10)

(a) State the total number of times pattern is called when pattern(3) is executed, including the first call. [1]

(b) Trace the call pattern(3) and state the complete output, one value per line, in order. [3]

(a) 4 (calls with n = 3, 2, 1, 0)(1)
(b) 3, 2, 1 output first, in that order (before the recursive calls are made)(1)
* output after 1 (output by the base case call pattern(0))(1)
10, 20, 30 output last, in that order (as the calls unwind) (all seven values in correct order: 3 2 1 * 10 20 30; do not award this mark for 30, 20, 10)(1)
Answer: (a) 4 (b) 3, 2, 1, *, 10, 20, 30
Examiner tip: The print after the recursive call only runs as each call returns, so the innermost (n = 1) prints first: 10, 20, 30, not 30, 20, 10.

Stuck on Recursion and quicksort (HL)?

Get it sorted in a free 30-minute session

We work through your weakest questions on this topic on Zoom. I reply the same day.

Free 30-min session on this topic Send me 5 questions a day

4StandardHL only4 marks

A recursive function count_char(text, ch) returns the number of times the single character ch appears in the string text. For example, count_char("banana", "a") returns 3 and count_char("", "a") returns 0.

Construct the function count_char using recursion. Loops and built-in counting methods (such as count()) must not be used. [4]

Base case: if text is empty (text == "" / len(text) == 0) return 0 (accept a correct single-character base case that returns 1 or 0 as appropriate)(1)
Compares the first character with ch (text[0] == ch) (allow the last character, text[-1], with the matching slice)(1)
Recursive call on the rest of the string, i.e. a shorter string (count_char(text[1:], ch)) (allow an index parameter that increases towards len(text))(1)
Adds 1 to the result of the recursive call when the character matches, and returns the result of the call unchanged otherwise (both paths must return a value; deduct if the result of the recursive call is not returned)(1)

Examiner tip: Students often call the function recursively but forget to return its result, so the count is lost; every path must end in a return.

5StandardHL only5 marks

The following Python function implements quicksort.

def quicksort(items):
    if len(items) <= 1:
        return items
    pivot = items[0]
    left = [x for x in items[1:] if x < pivot]
    right = [x for x in items[1:] if x >= pivot]
    return quicksort(left) + [pivot] + quicksort(right)

The function is called with the list [42, 17, 63, 8, 55, 29, 71].

(a) State the value of pivot in the first call. [1]

(b) State the contents of left and right in the first call. [2]

(c) Explain why the list returned by the first call is in ascending order, given that the two recursive calls each return a sorted list. [2]

(a) 42(1)
(b) left = [17, 8, 29] (order must be as shown, i.e. original order kept)(1)
right = [63, 55, 71](1)
(c) Every item in left is less than the pivot and every item in right is greater than or equal to the pivot, so the pivot is in its correct final position between them(1)
As left and right are each sorted (by the recursive calls), joining sorted left + pivot + sorted right gives a fully sorted list (accept: divide-and-conquer description that links the partition to the concatenation)(1)
Answer: (a) 42 (b) left = [17, 8, 29], right = [63, 55, 71] (c) pivot ends in final position; sorted left + [pivot] + sorted right is sorted
Examiner tip: The list comprehensions keep items in their original order, so left is [17, 8, 29], not [8, 17, 29]; the sublists are only sorted later by the recursive calls.

6HardHL only5 marks

The diagram shows the tree of calls made when the quicksort function below is called with [5, 9, 2, 7, 1, 8, 3]. Each box shows the list passed to one call. A left branch is the call on left; a right branch is the call on right.

def quicksort(items):
    if len(items) <= 1:
        return items
    pivot = items[0]
    left = [x for x in items[1:] if x < pivot]
    right = [x for x in items[1:] if x >= pivot]
    return quicksort(left) + [pivot] + quicksort(right)

(a) State the lists represented by A, B, C and D. [2]

(b) State the total number of times quicksort is called. [1]

(a) Any two of A = [9, 7, 8], B = [3], C = [7, 8], D = [8] correct(1)
All four of A, B, C and D correct (lists must be in the order shown: elements keep their original order, e.g. A = [9, 7, 8], not [7, 8, 9])(1)
(b) 9 (count each box, including the two calls with an empty list)(1)
(c) In A = [9, 7, 8] the pivot (9) is the largest value in the list, so every other item goes into left and right is empty / the partition is unbalanced(1)
So the list size only decreases by one each level, giving an extra level of calls ([7, 8] then [8]); in the left side the pivot 2 is the middle value and splits [2, 1, 3] evenly into two single items (accept: pivot near the median gives balanced partitions and fewer levels)(1)
Answer: (a) A = [9, 7, 8], B = [3], C = [7, 8], D = [8] (b) 9 (c) pivot 9 is the largest item so the partition is unbalanced; the left pivot 2 is the median
Examiner tip: Count the calls on empty lists too: they are real calls that hit the base case.

7StandardHL only5 marks

A student writes the recursive function below to add the integers from 1 to n.

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

sum_to(500) returns 125250, but sum_to(100000) stops with a RecursionError.

(a) Explain why sum_to(100000) fails. [2]

(b) Suggest how the student could calculate the same value for large n without this error. [1]

(c) The student's next task is to draw a fractal tree, in which each branch splits into two smaller branches that look like the whole tree. Explain why recursion is suitable for this task. [2]

(a) Each call is added to the call stack as a stack frame (holding n and the return address) and is not removed until the calls below it return / the base case is reached(1)
100000 nested calls are needed, which exceeds the maximum recursion depth / stack size (Python's default limit is about 1000), causing a stack overflow (accept: runs out of stack memory)(1)
(b) Use iteration, e.g. a loop that adds 1 to n to a running total (accept: use the formula n(n + 1)/2; accept: use sum(range(n + 1)); do not accept 'increase the recursion limit' alone, as the stack may still overflow)(1)
(c) The problem is self-similar: each branch is a smaller version of the whole tree, so the same function can be called again with a smaller size/length(1)
Recursion therefore gives shorter, clearer code that mirrors the structure of the problem / is easier to write than tracking every branch with loops and a manual stack; with a base case such as a minimum branch length to stop it (any one advantage linked to the fractal)(1)
Answer: (a) Each call uses a stack frame; 100000 frames exceed the recursion limit/stack, causing stack overflow (b) Use a loop (or n(n+1)/2) (c) Fractal is self-similar so recursion matches it, giving simpler code
Examiner tip: 'It uses too much memory' is not enough: link the failure to one stack frame per call and the stack (recursion depth) limit being exceeded.

8HardHL only5 marks

The quicksort function below always uses the first item as the pivot.

def quicksort(items):
    if len(items) <= 1:
        return items
    pivot = items[0]
    left = [x for x in items[1:] if x < pivot]
    right = [x for x in items[1:] if x >= pivot]
    return quicksort(left) + [pivot] + quicksort(right)

Assume that, in each call that partitions a list, every item other than the pivot is compared with the pivot exactly once.

(a) Calculate the total number of comparisons made when the function sorts the list [1, 2, 3, 4, 5, 6, 7, 8]. Show your working. [2]

(b) Sorting [5, 2, 7, 1, 3, 6, 8, 4] with the same function needs only 13 comparisons. Explain why the list in (a) needs more comparisons. [2]

(a) Partitions of size 8, 7, 6, …, 2 give 7 + 6 + 5 + 4 + 3 + 2 + 1 (allow method shown as (n − 1) + (n − 2) + … + 1 or n(n − 1)/2 with n = 8)(1)
= 28 comparisons(1)
(b) The list is already sorted, so the first item is always the smallest; every other item goes into right and left is empty(1)
So each call only reduces the list by one item, giving n − 1 levels of calls; this is the worst case, O(n²), compared with roughly balanced partitions (about log₂ n levels, O(n log n)) for the mixed list (accept: worst case vs average case with correct Big O)(1)
(c) Choose the middle item / a random item / the median of the first, middle and last items as the pivot (do not accept 'the last item', which has the same problem for sorted lists)(1)
Answer: (a) 7 + 6 + … + 1 = 28 (b) Sorted list: first-item pivot is always the smallest, so partitions are maximally unbalanced (worst case O(n²)) (c) Use the middle, a random or median-of-three pivot
Examiner tip: Don't count a comparison for the single-item calls: a list of length 1 is a base case and is not partitioned.

9StandardHL only5 marks

The recursive function below uses Euclid's algorithm to find the greatest common divisor (GCD) of two positive integers.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

(a) Trace the call gcd(252, 105) by stating the arguments of every call made, in order. [2]

(b) State the value returned by gcd(252, 105). [1]

(d) Outline what is stored in a stack frame when gcd calls itself. [1]

(a) gcd(252, 105) → gcd(105, 42)(1)
→ gcd(42, 21) → gcd(21, 0) (allow follow-through for one arithmetic slip in a % b)(1)
(b) 21(1)
(c) 4(1)
(d) The values of the parameters/local variables (a and b) and the return address (where execution continues when the call returns) (either one of parameters/local variables or return address with the other implied)(1)
Answer: (a) (252, 105), (105, 42), (42, 21), (21, 0) (b) 21 (c) 4 (d) Parameters/local variables and the return address
Examiner tip: Show every call, including the base-case call gcd(21, 0); stopping at gcd(42, 21) loses a mark and gives the wrong stack depth.

10StretchHL only7 marks

A sorted list is stored as data = [4, 9, 15, 22, 30, 37, 41, 56] (indices 0 to 7). A programmer writes this recursive binary search, which should return the index of target, or -1 if it is not present.

def bsearch(data, target, low, high):
    mid = (low + high) // 2
    if data[mid] == target:
        return mid
    elif data[mid] < target:
        return bsearch(data, target, mid, high)
    else:
        return bsearch(data, target, low, mid - 1)

(a) Trace bsearch(data, 37, 0, 7), stating the values of low, high and mid in each call, and state the value returned. [2]

(b) Explain what happens when bsearch(data, 50, 0, 7) is executed. [2]

(a) Call 1: low = 0, high = 7, mid = 3 (data[3] = 22 < 37); call 2: low = 3, high = 7, mid = 5(1)
data[5] = 37 so 5 is returned (and passed back unchanged through call 1)(1)
(b) Calls go (0, 7) mid 3 → (3, 7) mid 5 → (5, 7) mid 6 → (6, 7) mid 6; since 41 < 50 and low is set to mid (not mid + 1), the call (6, 7) is repeated with the same arguments for ever(1)
Infinite recursion: the base case is never reached, so stack frames build up until a stack overflow / RecursionError occurs (it never returns −1) (accept: no base case for target not found)(1)
(c) Adds a base case at the start: if low > high: return -1 (must be checked before data[mid] is accessed)(1)
Changes the first recursive call to bsearch(data, target, mid + 1, high)(1)
All other logic retained so the function works and every recursive call is returned (e.g. found returns mid; else branch unchanged with mid − 1)(1)
Answer: (a) (0, 7, 3), (3, 7, 5); returns 5 (b) Infinite recursion at (6, 7), mid 6: stack overflow / RecursionError (c) add if low > high: return -1 first; use mid + 1 in the first recursive call
Examiner tip: Two separate faults are needed in (c): a 'not found' base case alone still loops at (6, 7) because low never passes mid; you must also use mid + 1.

Stuck on this topic?

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.

Free 30-minute session