Elementary Recursion with Robots

Site Index

Purpose

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

Prerequisites

Understanding of Chapter 6 of Algorithms and Data Structures: The Science of Computing, particularly sections 6.1 through 6.4.

Background

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.

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 recursive methods that solve each of the problems described below. The first five 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.

Find a Red Tile

Design and code a recursive algorithm that causes a robot to move forward until it is standing on a red tile. If the robot is initially standing on a red tile, it should not move at all. Assume as a precondition that there is at least one red tile between the robot and whatever wall it is facing (although the red tile may be at the robot’s initial position).

Red Line

Design and code a recursive algorithm that makes a robot draw a straight red line n tiles long, where n is a parameter to the algorithm. Assume as preconditions that n >= 0, the robot is initially standing on what will be the first tile of the line, facing in the direction the line should grow, and that there are no obstructions on the n tiles in front of the robot.

Red Diagonal

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:

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.

Spiral

Design and code an algorithm that makes a robot draw draw a red, square-cornered, spiral, in which the first side is n tiles long, and each subsequent side is 1 tile shorter than the previous side. In other words, the second side is n - 1 tiles long, the third n - 2, etc. The length of the first side, n, is a parameter to the algorithm. Assume as preconditions that n >= 0, and that there are no obstructions within the spiral’s bounding box (i.e., within the smallest rectangular group of tiles that contains the spiral).

For example, here is a robot that has just finished drawing a square spiral whose first side is 7 tiles long:

Squaring

Design and code a recursive algorithm that computes n², where n is an integer parameter to the algorithm. The recursion should be based on the fact that, when n > 0, n² = (n-1)² + 2n - 1. When n = 0, n² = 0 too. Assume as a precondition that n >= 0.

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

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

Site Index