Lab 4 — Intermediate Recursion

Purpose

Prerequisites

Background

This laboratory exercise involves designing and coding a series of recursive algorithms. Two 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.

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

Strings

The “Palindromes” exercise requires manipulating strings. Strings in Java are objects, instances of the standard library class String. Some messages to strings that are likely to be particularly useful in this exercise are described below.

(The descriptions use a convention that is widely used in user documentation of messages: each message is introduced by showing how it could be declared inside the class that implements it. Note that this is not what a programmer writes in order to use the message, rather it is a compact way to provide complete information on the message’s name, the number and types of parameters, the type of result, etc. For example, the message description “char charAt( int i )” says that there is a message named “charAt”, which has one parameter, that parameter is an integer, and the message returns a character. A programmer can thus deduce that uses of this message could look like c = obj.charAt(7), or System.out.println( obj.charAt(i) ), and so forth, where c is a char variable, i is an integer variable, and obj is whatever sort of object handles the charAt message — a String in this particular case.)

int length()

This message returns the number of characters in a string. For example, the following assigns the number of characters in string someString to variable count:

    int count = someString.length();

char charAt( int i )

This message extracts and returns the i^th character of a string. Character positions are numbered from 0. For example, the following assigns the second character of someString to variable c:

    char c = someString.charAt( 1 );

String substring( int first, int end )

This message extracts and returns the portion of a string that starts with the character at position first in the string, and extends to but doesn’t include the character at position end. Character positions are numbered from 0. Thus, the following extracts the first 3 characters from string someString:

    String firstThree = someString.substring(0,3);

For more information about the String class, see the Online Java API Documentation maintained by Sun Microsystems.

Exercise

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

Pyramid

A pyramid is a roughly triangular pattern of painted tiles, such as the following:

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.

Bouncing

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 n^th tile from the wall, then the robot ends on the 2n^th 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 n^th tile from a wall, facing that wall, there are no obstacles on the n tiles behind the robot.

Palindromes

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.

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, October 4. Turn in a printout showing the methods you wrote for each exercise, as well as the main method. The main method should show all the tests you used to check that the other methods work, although some of the tests can be commented out.

Copyright © 2004. Charles River Media. All rights reserved.

Revised Sept. 22, 2004