Recursion is the use of a procedure within itself. That definition is simple enough, but using recursion in real programming takes some practice and also requires care in the order in which ideas are presented.
Recursion is one of the two signature big ideas that distinguish BJC from other CS Principles courses. You never truly need recursion to solve a problem, and even AP CS teachers have traditionally had trouble learning it, so why do we make it so central to our curriculum?
One of the central insights of the CS equity and inclusion movement that led to the design of CS Principles is that nontraditional CS students, especially young women, have had a stereotyped view of programming as boring, lonely work, but even people with that stereotype actually love computers, in the form of cell phones, video games, and social networking. That's why the framework makes programming just one of seven "big ideas" of computer science — you meet kids where they are.
We agree: You meet kids where they are. But we're not willing to declare victory if we end up leaving them where they start. The truth is, computer science is about programming. The other stuff is important, too, but there wouldn't be a field of computer science if computers could program themselves. We want kids to complete the course having come to see programs themselves, not merely the results of running the programs, as beautiful and joyous. And we think that recursion is the place in the curriculum where that happens: Kids see a tiny recursive program that produces an enormously complicated effect, and that's the central "Aha!" moment in learning to program. Variable assignment and conditionals and loops just don't have that power.
Unit 5 introduces recursion in the context of command blocks, which are recursive programs that have a visible effect. More specifically, this unit revolves around fractal graphics, i.e., pictures that include smaller, simpler versions of themselves. The canonical example is the fractal tree, in which each branch is a smaller sub-tree with branches of its own.
The program that produces this tree is not trivial, and we build up to it in small steps in Lab 1. We expand to other fractal shapes, and gradually reduced hand-holding, in Lab 2. Those two labs are the entire programming content of this unit, so it's smaller than the earlier ones, but you should expect to progress more slowly through each lab.
A more traditional approach to teaching recursion would start with tail recursion, in which the sole recursive call comes at the end, like this:
It is said that students understand this sort of recursion more easily than the branching recursion of the fractal tree. But the truth is that students misunderstand this code! They think the recursive call at the end means "go back to the beginning." This wrong model will work for tail recursive blocks like this version of
square, but eventually students see a recursive call that isn't at the end of the definition, and then they're lost. The "go back" model is hard to overcome once it invades a learner's mind. Better to start with an example in which "go back" obviously fails.
Also, a student looking at this definition will wonder what the point is of doing in such a complicated way the same task they did with
repeat 4 in the first unit.
tree2; and so on.) Students go through this sequence with no feeling of cheating, since, for example,
tree3has been written and debugged completely before we use it in
tree4. The combining method is time-consuming, but it's worthwhile for students to use it throughout this lab as they make variants on the simple tree.