Laboratory Exercise

Recursion

Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)

Site Index

Purpose

This exercise develops students’ability to design and code recursive algorithms.

Prerequisites

{Prerequisites}

Background

This laboratory exercise asks students to design and code a series of recursive algorithms for the robot introduced in Chapter 2 of Algorithms and Data Structures: The Science of Computing.

Recursion

Chapter 6 of Algorithms and Data Structures: The Science of Computing introduces recursion. This laboratory concentrates on aspects of recursion discussed in sections 6.1 through 6.5.

Robots

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.

Several of the methods students write in this exercise need 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 );

Constructors in Subclasses

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 );

Exercise

Design and code a subclass of Robot that provides the recursive methods described below. Also write a main program that tests your methods.

Blue Diagonal

Design and code a recursive algorithm that makes a robot draw a diagonal blue 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 southeast 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 right corner of its room:

[Diagonal Blue Line to the North and West of Southeast Corner]

Counting Red Tiles

Design and code a recursive algorithm that moves a robot forward until it comes to a wall, and returns the number of red tiles that the robot encounters on the way, including any red tile that the robot starts on, and any that is next to the wall.

Striped Lines

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 obstructions 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]

Colorful Line

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 magenta, the middle tile is orange, and the last n tiles are light blue. (These colors are available as constants Color.magenta, Color.orange, and Color.cyan from Java’s library class Color.)

For example, here is a colorful line with n = 2. The robot started where the bottom magenta tile is, and ended (as shown) on the top light blue one:

[Two Light Blue Tiles Above One Orange Above Two Magenta]

Final Details

The Robot Class

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.

Submitting Your Work

This lab is due at the start of your lab session on Monday, February 16. Turn in printouts of your subclass and main program.

Copyright © 2004 Charles River Media. All rights reserved.

Revised Feb. 5, 2004 by Doug Baldwin

Site Index