![[Spiral Sides Overlap at Corners]](img/note-reclabs-1.gif)
Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
These notes discuss the “Elementary Recursion” and “Intermediate Recursion” laboratory exercises. Both of those labs develop students’ abilities to design recursive algorithms of the sort discussed in Chapter 6 of Algorithms and Data Structures: The Science of Computing.
These labs nominally correspond to two laboratory sessions, one exploring more challenging uses of recursion than the other. However, the material in the labs can actually be given to students in many forms, allowing instructors flexibility in how many lab sessions they spend on recursion, exactly what exercises they ask students to do, etc.
Although one lab is labelled “elementary” and the other “intermediate”, the distinction is somewhat arbitrary. The real distinction is that the elementary exercises are appropriate for students’ first experiences writing recursive algorithms, while the intermediate ones are better suited for students who have had some prior experience designing recursions. For the most part, the elementary recursions are tail recursions, while the intermediate exercises use recursion in more sophisticated ways, but still only require writing one recursive statement per algorithm. However, neither lab follows this guide strictly (for example, the counting red tiles and squaring exercises in “Elementary Recursion” aren’t tail recursions, while the palindrome exercise from “Intermediate Recursion” can be).
Both labs contain more than enough exercises for one lab session. This allows instructors to create semi-custom labs by picking a subset of the exercises (4 or 5 is probably a good number for a 2-hour lab) to actually do.
Instructors who do two labs on recursion can use “Elementary Recursion” for the first, and “Intermediate Recursion” for the second. Instructors in faster-paced courses may only do one lab on recursion. In this case, assigning a mixture of exercises from both the elementary and intermediate labs is fine — students who understand the algorithms in Section 6.5 of Algorithms and Data Structures: The Science of Computing, or who have designed similar algorithms in lectures, should be able to do intermediate exercises in their first lab on recursion. For instructors who want, the exercises can also be repackaged to make three labs on recursion.
The problems in the intermediate exercise can also be mixed with problems from the Intermediate Recursion with Line Drawings exercise, providing further variety in the number or nature of laboratory exercises available for a course. This is particularly convenient for instructors who want to expose students to as large a variety of applications of recursion as possible.
In general, we feel that courses should move quickly from introducing the basic concept of recursion to introducing the mathematical tools for reasoning about it (i.e., Chapter 7 of Algorithms and Data Structures: The Science of Computing). Induction in particular is a very productive tool for thinking about recursion, and therefore something students should learn in close conjunction with recursion. To avoid overwhelming students with too many new ideas at once, we recommend introducing recursion as an algorithm design idea first, and later introducing induction, but induction should come as soon as students are comfortable enough with the basic concept of recursion to learn a new way of approaching it.
These labs do not explicitly talk about induction, but the preconditions and postconditions that “Intermediate Recursion” asks students to state for its robot algorithms are starting points for such reasoning. Specifically, if students think about recursive messages in these algorithms as things that produce certain postconditions relative to a smaller problem (i.e., as things that satisfy an induction hypothesis), they will have a much easier time correctly writing the code around the recursive messages. Instructors can exploit this point to introduce inductive reasoning into their course while students practice the basics of recursion. Ways of doing this range from discussing (either during or immediately after lab sessions) how the preconditions and postconditions help one design the algorithms, to asking students to write comments explaining how the code before a recursive message establishes the message’s preconditions and the code after a recursive message builds on the message’s postconditions, to asking students to write full correctness proofs for the algorithms they design.
Many of the exercises in these two labs have idiosyncracies or distinctive problems that students may encounter.
These are both deliberately very simple algorithms. One or both make good “warm up” exercises.
The red line algorithm can be used in the spiral exercise later, as discussed below.
Many students will want to use some sort of explicit counter in this algorithm. Their algorithms will use recursion to move a robot to a wall, but will use a parameter to accumulate a count of red tiles, or will accumulate a count in a global variable. Some students may try to count in a local variable, which they will discover doesn’t work, although they may need to be told why. More elegant recursions compute the result as the recursion returns, by adding one to the recursive result whenever the robot starts on a red tile. Instructors should encourage students to think of the recursion in this manner.
Students sometimes don’t realize that “return” is a technical term that describes how an algorithm communicates its result to its client. These students assume that the algorithm for counting red tiles can simply print its result. However, an important reason for including this exercise in the lab is to give students a chance to practice writing a recursive algorithm that calculates and returns (in the technical sense of the word) a result, and instructors should insist that students’ algorithms do so.
Drawing spirals involves recursion in two places: first, a spiral whose first side is n tiles long contains a total of n sides, and so can be drawn by drawing one side and then recursively drawing the remaining ones. Second, each side contains multiple tiles, and so can be drawn by painting one tile and then recursively drawing the rest of the side. The first recursion is easily incorporated into the “spiral” method proper; the second can be handled by having “spiral” call the “red line” method described earlier in the lab.
Although not immediately apparent, a spiral whose first side is n tiles long really does have n sides. The last side, of length one, completely overlaps the last tile of the length 2 side, as illustrated below. Instructors may need to point this fact out to students.
This is one of the few exercises in these labs that does not involve the robot. We concentrate on the robot because it should be familiar to students when they reach this lab, and fun for them to work with. However, it is worthwhile for students to experience recursion in other environments too, and this exercise is an opportunity to do that.
Many students have trouble seeing how to use recursion to solve this problem. The problem description in the lab is explicitly recursive, defining n2 in terms of (n-1)2. However, many students seem to read “(n-1)2” simply as meaning (n-1) multiplied by itself, and do not identify it as recursion in this definition. The fact that recursion is so hard to recognize in this form makes this an important exercise, but instructors may have to help some students identify the recursion.
These are both easiest to do with a single recursion that uses the “inversion” pattern discussed in Section 6.5. However, some students will be tempted to use two recursive methods, one to draw each half of the figure. Instructors should help these students discover the cleaner algorithms.
A striped line of n > 1 tiles recursively contains a striped line of n - 2 tiles. Thus, the recursion students write for this algorithm will have a form that is not explicitly demonstrated in Chapter 6 of Algorithms and Data Structures: The Science of Computing, but that is an interesting extension of the forms illustrated in that chapter. In particular, the algorithm should have two base cases (n = 0 and n = 1), and a recursive message whose parameter is of the form n - 2 rather than n - 1. Many students will need help seeing this recursion. Often, helping these students identify the recursive structure of the lines enables them to complete the algorithm design and coding on their own.
Like the colorful line and pyramid, this problem can use the “inversion” pattern to good effect. Here, however, the work done after the recursive message is not symmetric to the work done before: the robot should move two steps away from the wall for every one step taken towards it.
Like squaring, this problem illustrates a non-robot application of recursion.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin