MskProdComputing
Back to the topic

The mark scheme starts on a new page, so you can print pages one and two for a student and keep the last page yourself. Everything prints in black on white whichever theme you are using.

Python · A Level 1

Recursion

Section A: 10 multiple choice questions, 10 marks. Section B: 5 written questions, 20 marks. Total 30 marks.

Name

Class

Date

Mark  / 30

Section A

Circle the letter of the correct answer. One mark each.

  1. 1What two parts must every recursive subprogram have?1
    1. AA base case, and a recursive case that moves closer to it
    2. BA loop, and a counter
    3. CA global variable, and a return statement
    4. DA parameter, and a local variable
  2. 2What happens when a recursive function has no reachable base case?1
    1. AThe function returns 0 once it gets bored
    2. BThe call stack fills up and a stack overflow error occurs
    3. CThe program compiles faster
    4. DThe function becomes an infinite loop that uses no memory
  3. 3What does factorial(4) return, given factorial(n) returns 1 for n <= 1, otherwise n * factorial(n - 1)?1
    1. A1
    2. B4
    3. C10
    4. D24
  4. 4Where does the computer store the parameters and return address of each call?1
    1. AIn the program counter
    2. BOn the hard disk
    3. CIn the CPU registers only
    4. DOn the call stack, in a stack frame
  5. 5Which is a disadvantage of recursion compared with iteration?1
    1. AIt can never solve the same problems as a loop
    2. BIt cannot be used with lists
    3. CEach call uses stack memory, so deep recursion can overflow the stack
    4. DIt makes code longer than a loop in every case
  6. 6In gcd(a, b), which returns a when b == 0 and otherwise gcd(b, a % b), what is the base case?1
    1. Agcd(b, a % b)
    2. Bb == 0
    3. Ca == 0
    4. Da % b
  7. 7Why is the naive recursive Fibonacci function slow for large n?1
    1. AIt cannot reach its base case
    2. BIt uses too many global variables
    3. CIt sorts the numbers first
    4. DIt recalculates the same values many times
  8. 8What does memoisation do?1
    1. ARemoves the base case
    2. BStores earlier results so they are not recalculated
    3. CConverts recursion into a loop automatically
    4. DIncreases the stack depth
  9. 9How many moves does the Tower of Hanoi need for 4 disks?1
    1. A8
    2. B12
    3. C15
    4. D16
  10. 10Which technique tries a path and undoes it if it reaches a dead end?1
    1. ABacktracking
    2. BHashing
    3. CIteration
    4. DMemoisation

Section B

Answer in the space provided. The number of marks tells you how many separate points to make.

  1. 1StateState what is meant by the base case of a recursive subprogram, and explain why every recursive subprogram needs one.3
  2. 2ShowThe subprogram shown is called with mystery(4). Show the sequence of calls, and the values that are returned, and state the value that is output.4
    Python
    def mystery(n):
    if n == 0:
        return 0
    return n + mystery(n - 1)

print(mystery(4))
  3. 3WriteWrite a recursive function called power that takes a number, base, and a whole number, exponent, that is 0 or more, and returns base raised to the power exponent. You must not use the ** operator or a loop.4
  4. 4ExplainExplain what a stack overflow is, and how it can happen in a program that uses recursion.3
  5. 5DiscussA programmer must write a subprogram to total the numbers in a list. Discuss whether the programmer should use recursion or iteration.6

Mark scheme

Section A

1A2B3D4D5C6B7D8B9C10A

Section B

1 State what is meant by the base case of a recursive subprogram, and explain why every recursive subprogram needs one. 3

One mark for each of the following, to a maximum of 3.

  • The base case is the case where the answer is returned without a further recursive call
  • Without a base case the subprogram would keep calling itself forever
  • This fills the call stack, causing a stack overflow

Model answer. The base case is the version of the problem that is small enough to be answered directly, so it returns a value without making another recursive call. Every recursive subprogram needs one because otherwise it would keep calling itself with no way to stop. Each call adds a stack frame, so the call stack would eventually be filled and the program would fail with a stack overflow.

2 The subprogram shown is called with mystery(4). Show the sequence of calls, and the values that are returned, and state the value that is output. 4

One mark for each of the following, to a maximum of 4.

  • Identifies that mystery(0) is the base case and returns 0
  • Shows the chain of calls from mystery(4) down to mystery(0)
  • Shows the returns unwinding, 0, 1, 3, 6, 10
  • States that the output is 10

Model answer. mystery(4) calls mystery(3), which calls mystery(2), then mystery(1), then mystery(0). mystery(0) is the base case and returns 0. The calls then return: mystery(1) returns 1 + 0 = 1, mystery(2) returns 2 + 1 = 3, mystery(3) returns 3 + 3 = 6 and mystery(4) returns 4 + 6 = 10. The value output is 10, which is the sum of the numbers from 1 to 4.

3 Write a recursive function called power that takes a number, base, and a whole number, exponent, that is 0 or more, and returns base raised to the power exponent. You must not use the ** operator or a loop. 4

One mark for each of the following, to a maximum of 4.

  • Defines a function with the two parameters
  • Has a base case: when exponent is 0 the result is 1
  • Has a recursive case that multiplies base by power of exponent - 1
  • Returns the result of the recursive case

Model answer.

Python
def power(base, exponent):
    if exponent == 0:
        return 1
    return base * power(base, exponent - 1)

print(power(2, 10))

When the exponent is 0 the answer is 1, which is the base case. Otherwise the function multiplies base by base to the power one less, so each call moves the exponent closer to 0. power(2, 10) returns 1024.

4 Explain what a stack overflow is, and how it can happen in a program that uses recursion. 3

One mark for each of the following, to a maximum of 3.

  • Each call to a subprogram adds a stack frame to the call stack
  • The call stack has a limited size
  • A recursive subprogram with no reachable base case, or too deep a recursion, uses up all of it

Model answer. Each time a subprogram is called, a stack frame holding its parameters, local variables and return address is added to the call stack, and it is only removed when the call returns. The call stack has a limited size. If a recursive subprogram never reaches its base case, or the recursion is simply too deep, the frames use up all the space available and the program fails with a stack overflow.

5 A programmer must write a subprogram to total the numbers in a list. Discuss whether the programmer should use recursion or iteration. 6

One mark for each of the following, to a maximum of 6.

  • Iteration uses a fixed amount of memory however long the list is
  • Recursion adds a stack frame for every item, so a long list could cause a stack overflow
  • A loop is quicker because there is no overhead of calling a subprogram repeatedly
  • A loop is simple and easy to trace and debug for this problem
  • Recursion could be shorter for a nested or tree shaped list
  • A reasoned conclusion: iteration is the better choice for a flat list

Model answer. For a simple list of numbers iteration is the better choice. A loop uses a fixed amount of memory, whereas a recursive solution adds a stack frame for each item, so a very long list could fill the call stack and cause a stack overflow. A loop is also quicker, because it avoids the overhead of making a subprogram call for every item, and it is simple to trace and debug. Recursion has the advantage of being shorter and closer to the definition of the problem, which would make it a better choice if the list were nested to unknown depth or tree shaped. Since the list here is flat, the programmer should use iteration.