Unit 6 Teacher Guide
BJC Home
Unit 6 Student Pages
Introduction to Teacher Guide
Purpose
This unit extends the technique of recursion, introduced in Unit 5, to reporters, allowing us to write recursive functions.
In a sense, there is nothing new here: Students learned about reporters in Unit 1, and about recursion in Unit 5. But experience has shown that students have more trouble writing recursive functions than they do with recursive commands. The fact that the recursive calls come inside a combiner function, as explained in Lab 1, makes it even more important to develop the "leap of faith" understanding of recursion than in an imperative (command script) program.
After the brief introduction in Lab 1, we do something counterintuitive: We dive right into branched recursive functions, in which each call gives rise to two or more recursive calls. Linear-recursive functions (those with only one recursive call) are easier to write, but we avoid starting with them for two reasons:
- Most linear-recursive functions could instead be implemented as loops, leading students to as "Why are we using this confusing technique instead of a simple loop?" Branched recursive functions do not lend themselves as easily to looping, so they're more compelling for students.
- With linear-recursive functions, it's easy for students to develop the "go back" model of recursion, as if it were a simple loop. That model is totally wrong for recursive functions (even linear-recursive ones), but once a student gets it into his or her head, it's hard to dislodge.
Week by week stuff
- Programming Lab 1: Introduction. This short lab consists of a Getting Started in which students experiment with simple recursive functions, followed by an explanation of how recursive reporters differ in structure from recursive commands, and more simple exercises.
- Programming Lab 2: Pascal's Triangle. This is our first branched recursive function, in which the code closely follows the idea that each number in the triangle is the sum of two numbers above it. A Getting Started page motivates Pascal's triangle using the standard example of choosing a committee from a class.
- Programming Lab 3: Number Representation. This example is actually linear-recursive, but the recursive solution is more elegant than any iterative method. It's here partly because the AP syllabus requires us to teach binary, and as usual the BJC approach is to turn an otherwise uninspiring topic into a programming project. But we also go beyond binary to show how the same algorithms can convert to and from any base.
- Programming Lab 4: Sorting. Students have already seen a quadratic-time sort algorithm in Unit 4;[Citation needed.] here we use branched recursion to introduce a faster algorithm, mergesort, which involves two recursive calls to sort half-size lists. A "Take It Further" at the end hints at the idea of O(n log n) algorithms.
- Programming Lab 5: Subsets. Finding all the subsets of a set is challenging in several different ways. One challenge is that the result is a list of lists, so students have to be careful to remember whether the input to a particular block is a set (a list of simple elements) or a list of subsets. The algorithm for enumerating subsets is tricky. And then the coding of the recursion has a tricky base case. This may be the hardest lab in the course.
- Programming Lab 6: Some Simple Ones. We end the unit by what will seem like a step backwards, to relatively simple linear recursions. But this important lab has a hidden agenda: The simple examples can be generalized into the higher-order functions of Unit 3. For students who've made it through the rest of Unit 6, this lab won't seem hard at all, but implementing higher-order functions is the big BJC idea that the rest of the world thinks kids can't do. As usual, it's the visual metaphors of Snap! that enable this simple treatment.
- Investigation: Ice Cream Shop Menu. This is basically the Cartesian cross product function, in the form of an enumeration of all possible results of choosing size, flavor, etc., of an ice cream serving. It's a challenging project, and should definitely not be attempted before Lab 5 (subsets).