Unit 7 Lab 1 Teacher Guide

Lab 1: Trees

Recursion is the use of a procedure within itself. The definition is simple, but learning to use recursion takes opportunity and practice; learning it well requires care in the order in which ideas are presented.

$Animation shows a fractal tree growing by doubling of the branches at each stage$ Unit 7 introduces recursion in the context of fractal graphics, i.e., pictures that include smaller versions of themselves. The canonical example is the fractal tree, in which each branch is a smaller sub-tree with branches of its own.

A note on terminology: Technically, no picture of a fractal is a fractal; the picture is just an approximation. A fractal is a limit, so a picture would have to have infinitely many levels. You might want to say this once but, as with any geometric figure, a good approximation shows us enough to picture the limit.

The work on trees walks students through steps that help them overcome the feeling that a recursive call is "cheating" because it uses a block that hasn't been fully written yet. To avoid this confusion, we start with a sequence of simpler (non-recursive) tree blocks, each of which calls the one before it (e.g., tree 2 calls tree 1; tree 3 calls tree 2; and so on.) A few students will want to jump immediately to the recursive version. Unless they are already quite comfortable with recursion from some other learning, it's worth going through this level-by-level once to feel the structure; starting on the next page they'll write recursive procedures directly.

The reason why we do not start with tail recursion, in which the sole recursive call comes at the tail end, like this

countdown(num){if (num=0) {say(Blastoff!)} else {say (num) for (1) secs; countdown(num-1)}}

is that students often misunderstand the recursive call at the end to mean "go back to the beginning." This wrong mental model works for tail recursive blocks, but fails when students confront (or must design) a recursive call that can't be at the end of the definition. Embedded recursion, in which the recursive call isn't the last thing in the script, provides a more resilient introduction.

The repetition on page 1 of is deliberate: the tactile experience of building almost the same script repeatedly helps students notice its structure, and helps them see the virtue of combining them into a single script using recursion. Resist the temptation to teach them shortcuts, like duplicating scripts and adjusting them.)

Pacing

The 4 required lab pages could be split across 2–4 days (70–140 minutes). Expected times to complete follow:

20–40 minutes (<1 class period) on Recursive Tree
20–40 minutes (<1 class period) on The Base Case
15–30 minutes (<1 class period) on Self-Check: Tree Inputs
15–30 minutes (<1 class period) on Self-Check: Tree Variations
If used, 30–60 minutes (about 1 class period) on Vary Your Tree* (depending on which problems are undertaken)

vee calling vee: a tree with many branches ending with square, hexagon or star shaped leaves

Prepare

Learning Goal: Get a collective introduction to recursion through the Vee project, which selects blocks to draw from a list of shape blocks that includes the vee block itself.
Before starting the lab pages:This unit begins with a teacher demonstration because the collective gasp when the first complex picture appears is unforgettable. Vee is a great introduction to recursion because its use of randomness lets you ignore completely the annoying detail of base cases in recursive code. Students who've seen the demo, therefore, aren't ready to write their own recursive programs, but they're motivated to work through the first lab.
- Before students get started, project Snap!, choose "Open..." from the File menu, and select "Vee" from the list of example projects.
- At this point, the list of shapes does not include Vee itself.
- Click the green flag several times and ask students to describe what the vee procedure does. Type the space key to show the block definition and discuss how the steps of the procedure generate the images that appear. Do not call students' attention to the fact that shapes is a list of blocks; if a student asks about it, just acknowledge that that's what it is.
- Then ask students, "What will happen if we add vee to the list of shapes?" Type the uparrow key to do this. You will likely hear answers such as "We'll sometimes get another v-shape on one of the ends."
- Then click the green flag a few more times, stopping after the first significantly complex image appears. Ask students, "What happened when the vee block called itself?" Don't worry about getting to a precise answer here; the idea is just to instill a sense of the power behind the simple process of calling a procedure from within itself.
Note that the list of blocks in the corner of the stage (shown right) is something the students won't have seen before, but resist the temptation to talk about it. Students will come to understand it by themselves because they've seen lists before and they've seen blocks before.

Lab Pages

Page 1: Recursive Tree.
- Learning Goals:
  - Revisit the idea of state transparency.
  - Develop a recursive program by first creating the program with several non-recursive blocks and then combining them into one recursive block to perform the same function.
- Discussion Questions:
  - What is state transparency? Why is it important? Have you run into issues with state transparency before? What happened and how did you resolve it?
  - Project the tree 2 block definition together with an image of the result and ask students to describe the role of each block on the resulting drawing. Do the same for tree 3.
  - These questions encourage students to attend closely to the details of how the trees are drawn and which aspects are essential to the structure and which are simply aesthetic choices:
    - Why are we multiplying size by 0.65 and 0.85? What if we used other values?
    - Why are we multiplying size by -1? What if we used a different value?
    - Why are we turning 25° CCW and then 25° CW and then 35° CW and then 35° CCW? What does that do? How could we simplify the code?
    - Why do we subtract 1 from the level in tree?
Page 2: The Base Case.
- Learning Goal: Learn the basic ideas and terms of recursion including base case, recursive case, and infinite loop.
- Discussion Questions:
  - Have students describe recursion in their own words.
  - Have students share their work on the last "For You To Do" problem, identifying the base case and recursive case in the final (corrected) tree script and describing how recursion works in this script.
- Tips:
  - A common student misconception is to think that when the base case is reached, that's the end of the entire recursion. That's true for some simple recursions, but definitely not in this case. Consider that every outermost branch of the tree comes from a base case. In fact, half of the calls to tree are base cases.
Page 3: Self-Check: Tree Inputs.
- Learning Goal: Learn to analyze edge cases.
- Tips:
  - These are thinking exercises—not programming exercises, but if there is a class debate, you can use Snap!'s visible stepping feature.
Page 4: Self-Check: Tree Variations.
- Learning Goal: Examine the inside of a recursive procedure.
- Tips:
  - Students shouldn't try to create these images as they are thinking through the exercises, but when they are finished, they can try.
  - You may wish to use input sliders and the "execute on slider change" feature in Snap!. You can learn about these features in the Snap! reference manual, Section XI.A in the subsection about the Settings menu.
Page 5: Vary Your Tree.
- Learning Goal: Explore and develop variations of the fractal tree.
- Discussion: After students work through the lab page, you may wish to have students share their favorite creations and the code behind them.
- Debugging: Random Tree

Related Resources:

These resources spend a lot of time with examples that could be done iteratively. They are provided as additional reading for teachers but not recommended for students.

Do we have replacement links for these commented-out ones? --MF, 6/24/21

Recursive Algorithms on Khan Academy