Worksheet

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

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

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

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

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

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

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)?

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

The task: down and back up

Write a recursive procedure echo(n), where n is a whole number from 0 upwards: - if n is 0 (the base case), print base and play tone(200, 0.2); - otherwise print down <n> and play tone(200 + 100 * n, 0.2), then call echo(n - 1), then print up <n> and play tone(200 + 100 * n, 0.2) again. Call echo(3). The output must be down 3, down 2, down 1, base, up 1, up 2, up 3, one per line, and you will hear the notes fall and rise again. Use no loops.

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

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

echo(3)

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/a2-2-recursion/
The simulator checks it and tells you when it passes. Nothing to install, no account.

Challenges

1. Trace sum_to(4) on paper as a table like the factorial one. How many frames are on the stack at its deepest?
2. Write a recursive power(base, exp) for whole-number exp of 0 or more. What is its base case?
3. Move the print in spiral to after the recursive call. Predict the output before you run it.