Lab 4 — Elementary Recursion

Purpose

Prerequisites

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

Binary (Base Two) Numbers

The “Binary Numbers” exercise below requires understanding how numbers are represented in base two, also known as binary. Binary is a way of writing numbers, much like the familiar base ten notation. As a preliminary to understanding binary, recall how base ten notation works: a base ten number consists of a series of digits, with the rightmost digit representing a number of ones, the next digit a number of tens, the third a number of hundreds, and so forth. Note that each digit position is associated with a power of ten: the rightmost with 10⁰, the next with 10¹, etc. For example, the base ten number 352 is interpreted as 3 x 100 + 5 x 10 + 2 x 1.

Binary works similarly, except that the digits are associated with powers of two instead of with powers of ten. The rightmost digit is still the ones digit, but the next digit is the twos digit, then the fours, and so forth. Thus, for example, the binary number 1101 is interpreted as 1 x 2³ + 1 x 2² + 0 x 2¹ + 1 x 2⁰ = 1 x 8 + 1 x 4 + 1 x 1 = 13 in base ten.

Strings

The “Binary Numbers” exercise also 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 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.

Counting Blue Tiles

Design and code a recursive algorithm that moves a robot forward until it comes to a wall, and returns the number of blue tiles that the robot encounters on the way, including any blue 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:

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 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:

Binary Numbers

Design and code a recursive algorithm that takes a string of binary digits (i.e., digits “0” or “1”) as its parameter, and that returns the integer that this string represents in base two. For example, if given the string “110” as its parameter, this algorithm would return 6. See “Binary (Base Two) Numbers” in the “Background” section for information on interpreting binary numbers. You may assume as a precondition that the parameter to this algorithm contains only the characters “0” and “1”.

Hint: Note that the strings “0” and “1” represent the integers 0 and 1, respectively. For longer strings, a string of the form “s0”, where s is a string of binary digits, represents two times whatever s represents, while a string of the form “s1” represents two times whatever s represents, plus 1.

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 on Monday, February 14. Turn in a printout of your robot subclass, main program, and binary number decoding method.

Also turn in (probably as comments in your code) a couple of sentences discussing 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.

Portions copyright © 2004. Charles River Media. All rights reserved.

Revised Feb. 6, 2005