← Back to course
Code Crew G5 / Week 03 / Monday
1/6
Week 03 · Nesting boxes

Monday

A box inside a box
// A function that calls itself
⏱ about 15 min

Monday: A box inside a box

A supply crate arrives from home base. A note on top says: the new star map chip is inside.

Rocket lifts the lid. Inside is another box. He opens that one. Inside is another box!

"How many boxes are there?" he groans. "I need a different plan for every box!"

Raven picks up the next box. "What do you notice about each box you open?"

Nova hovers over the pile. "Here is a hint. Maybe one plan works for every box."

One plan for every box

Here is the crate, drawn from the outside in. Each box holds one smaller box, until the last one.

Crate
↓
Big box
↓
Middle box
↓
Small box
↓
Tiny box: the star map chip!

Rocket does not need a new plan for each box. One plan works for all of them.

  1. To open a box, lift the lid.
  2. If the chip is inside, take it out and stop.
  3. If another box is inside, open that box using these same steps.

Look at step 3. The plan uses itself on a smaller box. This idea is called recursion.

Step 2 is just as important. It tells you when to stop.

THINK ABOUT THE BOX PLAN.
  • Read the question.
  • Tap your answer.
When does the plan stop?
What does step 3 do?
Count the boxes Rocket opens, from the crate to the tiny box. How many times does he follow the plan?
WHY THIS EXERCISEThe plan runs once for each box, and each run is on a smaller box.
Statement about the box planTrue or false?
The same three steps work for a crate with 100 boxes.?
Each box inside is bigger than the one around it.?
Without step 2, the plan would never say stop.?
WHY THIS EXERCISEA recursive plan needs a smaller problem each time and a clear place to stop.

Practice lab: smaller and smaller

A recursive plan has two parts. One part does a small step and uses the same plan on something smaller. The other part says when to stop.

A crate has 7 boxes in all, counting the crate. How many times does the plan run?
Rocket has opened 3 of those 7 boxes. How many are left to open?
Which step of the plan says stop? Type the step number.
Which step uses the plan again on a smaller box? Type the step number.
SMALLER COPY OR NOT?
  • Read the question.
  • Tap your answer.
To climb 10 stairs, climb 1 stair, then climb 9 stairs. Is the 9 stair job a smaller copy?
Which job is a smaller copy of put away 5 books?
A plan says: open the box, then open this same box again. What is wrong?
StatementTrue or false?
A recursive plan uses itself on a smaller problem.?
A recursive plan needs new steps for every box.?
The stopping step does not use the plan again.?
A crate of 3 boxes needs more runs than a crate of 6 boxes.?
WHY THIS EXERCISEThe plan runs once per box, and step 2 ends it.
Rocket's crate had 5 boxes. A new crate has twice as many. How many times will the plan run?
WHY THIS EXERCISEThe plan runs once for each of the 10 boxes, with the same three steps.

Wonderful! You just met recursion without a single line of code. Tomorrow we pass a question down a line of crew.