Answers

A2.3 Recursion versus iteration

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

What this lesson is about

The same algorithm both ways, the cost of a frame per call, repeated work, and stack overflow.

• The same algorithm, twice
• Turning recursion into a loop
• The cost of repeated work
• Stack overflow
• Comparing the two

Questions 5 marks in all

1. [1 mark]Why does a recursive solution usually use more memory than an iterative one?

   1. AEvery call that has not yet returned holds a stack frame
   2. BRecursive code is longer
   3. CLoops store their variables on disk
   4. DRecursion copies the whole program each call
   Answer: A. Recursion depth n means n frames on the stack at once; a loop reuses one set of variables.

2. [1 mark]Which are advantages of recursion over iteration?

   Tick every answer that is true.

   1. AIt can express self-similar problems, such as tree traversal, more naturally
   2. BThe code can be shorter and closer to the problem's definition
   3. CIt uses less memory
   4. DIt cannot cause a stack overflow
   Answer: A, B. Recursion's strengths are clarity for naturally recursive problems. It uses more memory and risks stack overflow.

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

   calls = 0
   
   def fib(n):
       global calls
       calls = calls + 1
       if n < 2:
           return n
       return fib(n - 1) + fib(n - 2)
   
   print(fib(5), calls)

   Answer:

   5 15

   fib(5) is 5, but the two recursive calls repeat work: fib(3) is worked out twice and fib(2) three times, 15 calls in all.

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

   def total_loop(n):
       result = 0
       while n > 0:
           result = result + n
           n = n - 1
       return result
   
   def total_rec(n):
       if n == 0:
           return 0
       return n + total_rec(n - 1)
   
   print(total_loop(6), total_rec(6))

   Answer:

   21 21

   Both add 6 + 5 + 4 + 3 + 2 + 1. The loop version keeps one result variable; the recursive one has seven frames at its deepest.

5. [1 mark]A recursive function to add up a list of 50,000 sensor readings crashes in Python, but a loop version works. Why?

   1. AThe recursion is too deep: it needs about 50,000 frames, beyond the limit on the call stack
   2. BRecursion cannot add numbers
   3. CThe loop version is compiled and the recursive one is not
   4. DThe list is too large to store
   Answer: A. One frame per item means a very deep call stack, which overflows. The loop needs no extra frames.

The task: binary, both ways

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

def to_binary_rec(n):
    return ""

def to_binary_loop(n):
    return ""

for n in [0, 1, 6, 37, 255]:
    print(f"{n}: {to_binary_rec(n)} {to_binary_loop(n)}")

from bugbot import *
connect()

def to_binary_rec(n):
    if n < 2:
        return str(n)
    return to_binary_rec(n // 2) + str(n % 2)

def to_binary_loop(n):
    if n == 0:
        return "0"
    digits = ""
    while n > 0:
        digits = str(n % 2) + digits
        n = n // 2
    return digits

for n in [0, 1, 6, 37, 255]:
    print(f"{n}: {to_binary_rec(n)} {to_binary_loop(n)}")