The worksheetDownload the PDF
Answers

A2.7 Thinking ahead and thinking logically

Recursion and computational thinking · A level · OCR H446 2.1.2, AQA 7517 4.4.1.1 · about 25 min

BugBotLab

What this lesson is about

Inputs, outputs and preconditions, caching and reuse, decisions and conditions, and solving logic problems.

Questions 6 marks in all

  1. [1 mark]What is a precondition?

    1. ASomething that must be true before a subroutine or algorithm runs for it to work correctly
    2. BThe first line of a program
    3. CA condition tested at the end of a loop
    4. DThe output an algorithm must produce
    Answer: A. For example, binary search has the precondition that the list is sorted.

  2. [1 mark]Which are drawbacks of caching?

    Tick every answer that is true.

    1. AThe cached copy can be out of date (stale)
    2. BIt uses extra memory or storage
    3. CDeciding what to keep and when to discard it adds complexity
    4. DRepeated requests are always slower
    Answer: A, B, C. Repeated requests are the ones caching speeds up.

  3. [1 mark]What does this program print?

    cache = {}
calls = 0

def fib(n):
    global calls
    calls = calls + 1
    if n in cache:
        return cache[n]
    if n < 2:
        answer = n
    else:
        answer = fib(n - 1) + fib(n - 2)
    cache[n] = answer
    return answer

print(fib(10), calls)
    Answer:
    55 19

    Each value from 0 to 10 is worked out once, and the second recursive call at each level is answered from the cache: 19 calls instead of 177.

  4. [1 mark]Why use reusable program components?

    Tick every answer that is true.

    1. AThey save development time
    2. BCode that has been used and tested many times is more reliable
    3. CA fault is fixed in one place for every program that uses it
    4. DThey are always faster than code written for one job
    Answer: A, B, C. A general component can be slower or larger than code written for one task; that is a trade-off, not a benefit.

  5. [1 mark]What does this program print?

    for culprit in ["Ada", "Bolt", "Cog"]:
    ada = culprit == "Bolt"
    bolt = culprit != "Bolt"
    cog = culprit != "Cog"
    if [ada, bolt, cog].count(True) == 1:
        print(culprit)
    Answer:
    Cog

    Only when Cog is the culprit is exactly one statement true (Bolt's), so the puzzle has one solution.

  6. [1 mark]Which constructs are enough to write any algorithm?

    Tick every answer that is true.

    1. ASequence
    2. BAssignment
    3. CSelection
    4. DIteration
    5. ERecursion
    Answer: A, B, C, D. Sequence, assignment, selection and iteration are the standard constructs. Recursion can always be replaced by iteration with a stack.

The task: routes with a cache

The robot moves on a grid, only ever one cell right or one cell up. routes(right_steps, up_steps) is the number of different routes from one corner to a cell that many steps right and up. Both parameters are whole numbers. If either is 0 there is exactly 1 route (a straight line); otherwise every route arrives either from the cell to the left or from the cell below, so routes(r, u) = routes(r - 1, u) + routes(r, u - 1). - Write routes recursively, with a dictionary cache so no pair is ever worked out twice. - Count every call of routes in a global calls, including calls answered from the cache. - Precondition: both parameters must be 0 or more. At the start of routes, if either is negative, raise ValueError with a message of your choice. Then print, in this order: 1. routes(3, 2) = <answer>; 2. routes(16, 16) = <answer>, with calls set back to 0 just before this call; 3. calls: <n>, the calls made by that one call (without a cache this would be over a billion); 4. refused: <message>, by calling routes(-1, 4) inside try and printing the error's message in except ValueError.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

cache = {}
calls = 0

def routes(right_steps, up_steps):
    if right_steps == 0 or up_steps == 0:
        return 1
    return routes(right_steps - 1, up_steps) + routes(right_steps, up_steps - 1)

print("routes(3, 2) =", routes(3, 2))

The hint students can ask for: Before any calculation, look the pair up in the cache and hand back the stored answer if it is there. After calculating, store the answer before returning it. The precondition check belongs at the very top, before the cache is touched. Reset the call counter just before the big call so it only counts that one.

A solution

from bugbot import *
connect()

cache = {}
calls = 0

def routes(right_steps, up_steps):
    global calls
    calls = calls + 1
    if right_steps < 0 or up_steps < 0:
        raise ValueError("steps cannot be negative")
    if (right_steps, up_steps) in cache:
        return cache[(right_steps, up_steps)]
    if right_steps == 0 or up_steps == 0:
        answer = 1
    else:
        answer = routes(right_steps - 1, up_steps) + routes(right_steps, up_steps - 1)
    cache[(right_steps, up_steps)] = answer
    return answer

print("routes(3, 2) =", routes(3, 2))
cache = {}
calls = 0
print("routes(16, 16) =", routes(16, 16))
print("calls:", calls)
try:
    routes(-1, 4)
except ValueError as error:
    print("refused:", error)

Any program that meets the task's checks is marked correct in the simulator; this is one way, not the only way.