← Back to course
Python 11-12 / Week 10 / Mission Quest
6/6
Week 10 · Recursion

Mission Quest

Mission Quest: Nested cups
// A base case, a smaller call, and a stack of calls to trace
⏱ about 30 min

Saturday: Mission Quest: Nested Cups

On Saturday the maker space is quiet. Comet brings a stack of paper cups, one tucked inside the next.

"Recursion, but you can hold it," she says. "Open a cup. If there is a smaller cup inside, do the same thing again."

Wren starts a tally on his clipboard. "What does the evidence say? We should count on the way back out, too."

Nova dims her lights and projects one small dot on the table. "How can I help?" she asks. "The smallest cup, with nothing inside, is your base case."

Comet hands you the stack. "Lead programmer, teach it to your family."

◇ OPEN AND CLOSE THE CUPS
You need: four or five cups, bowls or boxes that fit inside each other, plus paper and a pencil.
Nest them, smallest inside. Your family member holds the stack.
Open the outer cup and say "open 1". Open the next and say "open 2". Keep going.
When a cup has nothing inside, say "base case". Do not open anything more.
Now close back up, newest first, saying "close" with each number as you go.
Write down the order you said things. Then swap roles and do it again.
Last, explain recursion to your family member with the cups. Use the words base case and smaller problem.
CHECK THE CUPS
  • Read the question.
  • Tap your answer.
With four cups, which cup is closed first?
In the game, what is the base case?
PUT THE FOUR CUP GAME IN ORDER
  • ?close 3
  • ?open 2
  • ?open 1
  • ?close 4
  • ?open 3
  • ?open 4, base case
  • ?close 2
  • ?close 1
WHY THIS EXERCISEThis is a call stack: calls start going in, then finish in the opposite order.
For a grown-up
This week your student learned recursion: a function that calls itself on a smaller problem until it reaches a base case.
Ask your student to show you countdown or reachable in their fieldsim folder and explain which line stops it.
Talk about it: where else do you solve a big job by doing the same small job again and again?

Well done, lead programmer. Next week Nova shows the crew the same FieldSim ideas written in a new language, Java.

← Friday