![[Diagonal Red Line to the North and East of SouthWest Corner]](../../sc/img/lab-recursion1-1.gif)
Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004
This laboratory exercise asks students to design and code a series of recursive algorithms. Many, but not all, of these algorithms use the robot introduced in Chapter 2 of Algorithms and Data Structures: The Science of Computing.
The robot is available as a Java class named Robot (and a supporting
class named RobotRoom). Programs that use these classes need to
include two Java files: Robot.java and RobotRoom.java. The “Final
Details” section of this document explains how to find these files
and their documentation.
Any Java source file that refers to the Robot or RobotRoom classes
should “import” those classes, via the statement
import geneseo.cs.sc.*;at the beginning of the file.
One of the methods students write in this exercise needs to be tested in
rooms other than the default one (specifically, in rooms that have colored
tiles located in strategic places). There is
a RobotRoom constructor whose parameter is a string specification
for the room. This constructor can create the rooms needed in this lab. See
the documentation for RobotRoom for more information on
the constructor. Once an appropriate room exists, the four-parameter
constructor for Robot can place a robot in that room.
For example, the following statements first create a 3 tile wide by 10 tile
high (including walls) room with a red tile 2 rows below
the north wall in the center column, and then place
a robot
at the center of the south side of the room, facing the red tile:
RobotRoom room = new RobotRoom( "3 10 1 2 R" );
Robot occupant = new Robot( 1, 8, Robot.NORTH, room );A constructor is basically a method that initializes a new object (see Sections
3.4.2 and A.4.4 of Algorithms and Data Structures: The Science of Computing).
In Java, constructors have the same name as the class they initialize — for example, the constructors for Robot objects
are named Robot, the constructors for instances of a hypothetical ExtendedRobot subclass
of Robot would be named ExtendedRobot, and so forth.
Note that subclasses don’t inherit constructors from their superclass
the way they inherit other methods — for example, even if a constructor
for Robot logically does everything necessary to initialize instances
of an ExtendedRobot subclass, there is no way to automatically
apply this constructor to ExtendedRobot objects.
Even though Java doesn’t do it automatically, one often wants to initialize
instances of a subclass by just calling a superclass’s constructor. This
will probably be the case for the subclass of Robot defined in
this lab. To do this, define constructors for the subclass that do nothing
but call the corresponding superclass constructor. Within a constructor, the
word super can be used to call a superclass constructor. For example,
to allow instances of an ExtendedRobot subclass of Robot to
be initialized with their position, heading, and room (just like the four-parameter
constructor for Robot does), include the following constructor
in ExtendedRobot:
// Within the ExtendedRobot class...
public ExtendedRobot( int column, int row, int heading, RobotRoom room ) {
super( column, row, heading, room );
}A statement such as the following implicitly uses this constructor to initialize an extended robot:
ExtendedRobot r = new ExtendedRobot( 1, 3, Robot.NORTH, myRoom );Design and code recursive methods that solve each of the problems
described below. The first three problems involve robots, and their solutions
should be coded as methods of a subclass of Robot.
The last problem can be coded as a static method in the main class. Test each
algorithm in addition to simply writing code for it.
Design and code a recursive algorithm that causes a robot to move forward until it is standing on a green tile. If the robot is initially standing on a green tile, it should not move at all. Assume as a precondition that there is at least one green tile between the robot and whatever wall it is facing (although the green tile may be at the robot’s initial position).
Design and code a recursive algorithm that makes a robot draw a diagonal red line n steps long, where n is a parameter to the algorithm. Assume as preconditions that n >= 0, the robot is initially standing where the southwest tile of the line will be, facing north, and that there are no obstructions on the tiles that need to be colored for the line, or on any tile adjacent to those colored for the line.
As an example, here is a robot that has just drawn a 4-step diagonal. The robot started in the lower left corner of its room:
Design and code a recursive algorithm that moves a robot forward until it comes to a wall, and returns the number of tiles that the robot encounters on the way, including the tile that the robot starts on, and the one next to the wall (if these are the same tile, it should only be counted once).
Design and code a recursive algorithm that takes two integers, n and m, as parameters, and that returns the sum of the integers from n to m, inclusive. For example, if given 2 and 4 as parameters, the algorithm would return 9, because 2 + 3 + 4 = 9. Assume as a precondition that n <= m.
Students can download both Robot.java and RobotRoom.java from the Web.
Documentation on both classes is also available on the Web. The main documentation page is an index to documentation for all the Java classes written for use with Algorithms and Data Structures: The Science of Computing. To see the documentation for a specific class, click on that class’s name in the left-hand panel of the page.
This lab is due at the beginning of lecture on Tuesday, September 29.
Turn in printouts of the code you write, both the methods called for by the exercises and the main method that tests them (since you won’t necessarily want to test every method at once, you can turn in a main method with some of its statements commented out, if you wish).
As part of what you turn in (probably as comments in the code), comment in a couple of sentences on how the algorithms designed in this exercise fit the general form of recursive algorithms discussed in the text and lectures. For example, you might explain how the features that all recursive algorithms are supposed to have appear in these algorithms, whether the ways these algorithms use recursion are typical of all recursive algorithms, or whether other algorithms might use recursion differently, etc.
Copyright © 2004. Charles River Media. All rights reserved.
Revised Sep. 15, 2004