← Back to course
Python 11-12 / Week 10 / Wednesday
3/6
Week 10 · Recursion

Wednesday

Sim Lab: Reachable cells
// A base case, a smaller call, and a stack of calls to trace
⏱ about 30 min

Wednesday: Sim Lab: Reachable Cells

Comet spreads the field map across the bench. "Before Pip rolls, I want to know every cell it could ever reach from the start," she says.

Wren frowns at the rocks. "What does the evidence say? We could check by hand, but that is a lot of cells."

Nova projects the grid and lights up the start cell. "How can I help?" she asks. "From one open cell, Pip can try four neighbors. Each neighbor is a smaller version of the same question."

Comet sketches four arrows. "So the function calls itself four times!"

"And it must remember where it has been," Wren adds. "Or Pip will go back and forth forever."

They both look at you. "Lead programmer, build it."

The plan for recursion.py

This week, recursion.py joins your fieldsim folder. Today it gets three functions: countdown, total and reachable.

Tomorrow you will add three more. The field data, made-up data from the FieldSim story, comes from field_data.py.

# recursion.py
# Functions that call themselves (week 10).


def countdown(n):
    if n == 0:
        print("Go!")
    else:
        print(n)
        countdown(n - 1)


def total(nums):
    """Sum of a list, the recursive way."""
    if len(nums) == 0:
        return 0
    return nums[0] + total(nums[1:])


def reachable(grid, row, col, seen):
    """How many open cells the rover can reach from (row, col)."""
    if not grid.is_open(row, col) or (row, col) in seen:
        return 0
    seen.add((row, col))
    return (1 + reachable(grid, row - 1, col, seen)
              + reachable(grid, row + 1, col, seen)
              + reachable(grid, row, col - 1, seen)
              + reachable(grid, row, col + 1, seen))
  • reachable, at the bottom. Base case: the cell is not open (out of bounds or a rock), or Pip has already been there. That gives 0.
  • Otherwise, add the cell to seen and count 1 for it.
  • Then add what Pip can reach from each of the four neighbors: up, down, left and right.
  • seen is one set shared by every call, so a cell is never counted twice.
  1. Open a new file and save it in your fieldsim folder as recursion.py.
  2. Type the two header comment lines, then countdown from Monday and total from Tuesday.
  3. Add reachable below total, exactly as shown. Keep two blank lines between functions.
  4. Save. Make a new file, reach_demo.py, in the same folder.
  5. Type reach_demo.py, predict its output, then run it.
# reach_demo.py
# Try the functions in recursion.py.
from field_data import FIELD
from grid import FieldGrid
from recursion import countdown, total, reachable

countdown(2)
print(total([42, 18, 65]))
grid = FieldGrid(FIELD)
print(reachable(grid, 0, 0, set()))
PREDICT BEFORE YOU RUN
  • Read the question.
  • Tap your answer.
The field has 30 cells and 4 rocks. What will reachable(grid, 0, 0, set()) print?
2
1
Go!
125
26

Trace a tiny field next. A tiny 2 by 2 field makes the calls easy to follow. Row 1 starts with a rock.

# tiny_reach.py
from grid import FieldGrid
from recursion import reachable

tiny = FieldGrid(["..", "#."])
print(reachable(tiny, 0, 0, set()))
print(reachable(tiny, 1, 0, set()))
TRACE THE TINY FIELD
  • Read the question.
  • Tap your answer.
Which cells does reachable(tiny, 0, 0, set()) count?
Why does reachable(tiny, 1, 0, set()) give 0?
3
0

Change it once: wall off cells

set_cell changes the grid object only. FIELD in field_data.py stays the same, so the grid is your own copy of the field to change.

Add these lines to the end of reach_demo.py. Predict both numbers before you run it.

# reach_demo.py
# Try the functions in recursion.py.
from field_data import FIELD
from grid import FieldGrid
from recursion import countdown, total, reachable

countdown(2)
print(total([42, 18, 65]))
grid = FieldGrid(FIELD)
print(reachable(grid, 0, 0, set()))
grid.set_cell(0, 1, "#")
print(reachable(grid, 0, 0, set()))
grid.set_cell(1, 0, "#")
print(reachable(grid, 0, 0, set()))
print(FIELD[0])
PREDICT THE WALLS
  • Read the question.
  • Tap your answer.
After a rock at (0, 1), how many cells can Pip reach?
After rocks at (0, 1) and (1, 0), how many?
2
1
Go!
125
26
25
1
..*..#

Break it once, on purpose

In recursion.py, delete or (row, col) in seen from the first line of reachable, so it reads like this:

def reachable(grid, row, col, seen):
    """How many open cells the rover can reach from (row, col)."""
    if not grid.is_open(row, col):
        return 0
    seen.add((row, col))
    return (1 + reachable(grid, row - 1, col, seen)
              + reachable(grid, row + 1, col, seen)
              + reachable(grid, row, col - 1, seen)
              + reachable(grid, row, col + 1, seen))
PREDICT THE BREAK
  • Read the question.
  • Tap your answer.
What happens now when reachable runs?

Run reach_demo.py. The first four lines still print, then a very long traceback ends with this last line: RecursionError: maximum recursion depth exceeded

Put or (row, col) in seen back, save and run again. You should see 26 once more.

You built a recursive tool for the real field map, then broke it and fixed it. That is careful engineering, lead programmer.

← Tuesday