![[2 Red Tiles Above 1 Yellow Above 2 Blue]](img/lab-recursion2-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)
This exercise develops ability to design and code moderately complex recursive algorithms.
Understanding of Chapter 6 of Algorithms and Data Structures: The Science of Computing, particularly section 6.5.
This laboratory exercise involves designing and coding 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.
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 four 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.
Design and code an algorithm that has one integer parameter, n, and that causes a robot to draw a line of length 2n + 1 in which the first (i.e., closest to the robot's initial position) n tiles are blue, the middle tile is yellow, and the last n tiles are red. You may assume as a precondition that there are no obstacles on the tiles the line will occupy.
For example, here is a colorful line with n = 2. The robot started where the bottom blue tile is, and ended (as shown) on the top red one:
Adopt (and state as comments in the algorithm) additional preconditions and postconditions regarding where the robot will stand, and how it will face, relative to the line. These will be helpful in designing the code around the recursive message(s).
A pyramid is a roughly triangular pattern of painted tiles, such as the following:
![[A Green Pyramid in 3 Rows of Tiles]](img/lab-recursion2-2.gif)
The height of a pyramid is the number of rows of tiles in it. For example, the above pyramid has height 3.
Design and code an algorithm that makes a robot draw a pyramid of height n, where n is an integer parameter to the algorithm. Assume as a precondition that no walls will interfere with the robot drawing the pyramid. The main postcondition is that a height n pyramid is painted in the robot's room.
Adopt (and state as comments in the algorithm) additional preconditions and postconditions to say where the robot should be standing, and what direction it should be facing, relative to the pyramid. These pre- and postconditions will make it considerably easier to write the algorithm correctly.
Design and code a recursive algorithm that makes a robot draw a line in which the first, third, and other odd tiles are blue (counting the tile the robot started the line on as tile 1) and the second, fourth, and other even tiles are yellow. The algorithm should take the total length of the line, n, as a parameter. Assume as preconditions that n >= 0 and there are no obstacles within n tiles in front of the robot.
For example, here are two striped lines, one of length 5 and one of length 4. Notice that both start (at the bottom of the picture) with blue tiles, but the length 5 line ends with a blue tile, while the length 4 line ends with a yellow tile:
![[Alternating Blue and Yellow Tiles]](img/lab-recursion2-3.gif)
Design and code a recursive algorithm that moves a robot forward until it comes to a wall (or other obstacle), and then makes the robot “bounce” back to a tile twice as far from the wall as the tile the robot started on. More precisely, the relevant postcondition is that if the robot started on the nth tile from the wall, then the robot ends on the 2nth tile from the wall (counting tiles in such a manner that the tile immediately beside the wall is the first one from the wall). Assume as a precondition that when the robot starts on the nth tile from a wall, facing that wall, there are no obstacles on the n tiles behind the robot.
A palindrome is a string that reads the same backwards as it does forward. For example “radar” and “racecar” are both palindromes. Design and code a recursive algorithm that takes a string as its only parameter, and returns True if that string is a palindrome, and False if the string is not a palindrome.
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.
Turn in your solution to this exercise as directed by your instructor.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 8, 2005 by Doug Baldwin