Answers

A2.2 Recursion

Recursion and computational thinking · A level · OCR H446 2.2.1, AQA 7517 4.1.1.16, Eduqas A500QS 1.3 · about 25 min

What this lesson is about

Base case and general case, winding and unwinding, and a spiral the robot draws by calling itself.

• Base case and general case
• Winding and unwinding
• What goes wrong
• Recursion on the robot

Questions 6 marks in all

1. [1 mark]What is the base case of a recursive subroutine?

   1. AA case answered directly, with no further recursive call
   2. BThe first call made from the main program
   3. CThe case with the largest input
   4. DThe line that calls the subroutine again
   Answer: A. The base case stops the recursion. The line that calls itself is the general case.

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

   def f(n):
       if n == 0:
           return 0
       return n + f(n - 1)
   
   print(f(4))

   Answer:

   10

   f(4) = 4 + 3 + 2 + 1 + 0 = 10, built up as the calls unwind.

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

   def show(n):
       if n > 0:
           show(n - 1)
           print(n)
   
   show(3)

   Answer:

   1
   2
   3

   The print comes after the recursive call, so nothing is printed while winding. The numbers appear as the calls unwind, smallest first.

4. [1 mark]def count(n): return n * count(n - 1). What happens when count(3) is called?

   1. AIt never reaches a base case and ends in a stack overflow (a RecursionError in Python)
   2. BIt returns 6
   3. CIt returns 0
   4. DIt returns 3
   Answer: A. There is no base case, so every call makes another, until the stack runs out.

5. [1 mark]factorial(n) returns 1 if n == 0, otherwise n * factorial(n - 1). How many calls of factorial are made in total when the main program calls factorial(4)?

   Answer: 5. factorial(4), (3), (2), (1) and (0): five calls, and five frames at the deepest point.

6. [1 mark]Put the events of factorial(2) in the order they happen.

   Number the lines 1 to 5 to put them in the right order.

   1. factorial(1) returns 1
   2. factorial(0) returns 1
   3. factorial(1) calls factorial(0)
   4. factorial(2) calls factorial(1)
   5. factorial(2) returns 2
   Answer:

   factorial(2) calls factorial(1)
   factorial(1) calls factorial(0)
   factorial(0) returns 1
   factorial(1) returns 1
   factorial(2) returns 2

   All the calls wind down to the base case first; the returns then happen in reverse order.

The task: down and back up

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

def echo(n):
    print("down", n)

echo(3)

from bugbot import *
connect()

def echo(n):
    if n == 0:
        print("base")
        tone(200, 0.2)
    else:
        print("down", n)
        tone(200 + 100 * n, 0.2)
        echo(n - 1)
        print("up", n)
        tone(200 + 100 * n, 0.2)

echo(3)