Laboratory Exercise

Intermediate Recursion with Line Drawings

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

Purpose

This laboratory exercise develops ability to design and code moderately complex recursive algorithms.

Prerequisites

Understanding of Chapter 6 of Algorithms and Data Structures: The Science of Computing, particularly section 6.5.

Background

This lab involves designing and coding a series of recursive algorithms. Many, but not all, of these algorithms use a class that represents line drawings.

Line Drawings

This lab uses a class named LineDrawing, that represents drawings made from colored line segments. Each segment is straight, so the drawings nominally contain polygons and other angular figures. However, a number of very short straight segments joined end to end and heading in slightly different directions looks like a smooth curve, so the class can in fact be used to draw curves as well as straight-edged figures.

The line drawing class is formally introduced in Chapter 15 of Algorithms and Data Structures: The Science of Computing. For a summary of its abilities, see the sidebar entitled “A Line Drawing Class” in that chapter. However, the class is simple enough to be usable by anyone who understands basic object oriented programming.

Programs that use the LineDrawing class need to include a file named LineDrawing.java. See the “Final Details” section below for information on where to find this file and documentation for the class.

Any Java source file that refers to the LineDrawing class should “import” it, via the statement

Exercise

Design and code recursive methods that solve the problems described below. The first four problems involve line drawings, and their solutions should be coded as methods of a subclass of LineDrawing. The last problem can be coded as a static method in the main class.

Generally, each problem statement includes a precise description of the problem’s preconditions, and defines postconditions implicitly by describing the figure, or other result, an algorithm should produce. You may define additional postconditions for a problem if doing so helps you determine what code to write around recursive messages.

Valley

Design and code a recursive method for a subclass of LineDrawing that takes a natural number, n, as its parameter and draws a figure that looks somewhat like a cross-section of a valley with stepped sides. Each side should contain n steps. For example, here is a valley whose sides each have 3 steps:

The bottom of the valley can be the same width as one of the steps. The width and height of the steps can be any value.

Assume as a precondition that n >= 0. Also assume as preconditions that the pen is positioned where the left end of the valley figure should be, and that the pen is initially heading right.

Mountain Ranges

A mountain range is a series of these peaks, increasing in height from the ends into the middle. There is a single highest peak, which is the middle peak of the range. Here are two examples of mountain ranges:

Design and code a recursive method for a subclass of LineDrawing that draws mountain ranges. The algorithm should take two parameters. The first, n, is the number of peaks from one end of the range to and including the center peak. For example, the left-hand mountain range in the picture above has n = 3, while the right-hand one has n = 2. The second parameter is the length of the sides of the outer (i.e., lowest) peaks in the range.

Assume as preconditions that n >= 1, and that the pen is positioned where the left end of the mountain range should be.

Mirrored Curves

Define a “mirrored curve” to be two arcs from a circle. The arcs are mirror images of each other, reflected about a vertical line. The point at which the first arc ends is the beginning of the second. Note that in some cases the arcs cross each other. Here are some examples of mirrored curves:

Design and code a recursive algorithm for drawing mirrored curves. Code this algorithm as a method of a subclass of LineDrawing. The algorithm can draw a curve as a number of short, straight, segments, and the only parameter to the algorithm should be an integer n, which is the number of segments in one half of the curve (i.e., in one of the arcs).

Assume as preconditions that n >= 0, the pen is positioned where the mirrored curve should start, and the pen’s heading is the angle at which the first segment should be drawn.

Double Spirals

Define a “double spiral” to be a spiral joined at its inner end to a copy of itself. Here are some examples of double spirals:

The first spiral in these examples is red, and its copy blue. Notice that the blue and red spirals really are copies of each other, in that they could be rotated about the point where they connect in order to lie exactly on top of each other.

Design and code a recursive algorithm that draws a double spiral. Code this algorithm as a method of a subclass of LineDrawing. The algorithm can draw a spiral as a series of straight line segments, each of which heads at a slightly different angle than the previous one, and each of which is slightly shorter than the previous one. The algorithm should take the number of segments in one spiral (n) and the length of the first segment (length) as parameters.

Assume as preconditions that n >= 0, length > 0, and the pen is positioned at the outer end of the first spiral, heading in the direction that spiral’s first segment should head.

The two spirals may have different colors, as in the examples above, but don’t need to. The colors make it easier to tell where one spiral ends and its copy begins, but are not essential to the definition of double spiral.

Trees

For example, here, from left to right, are line-drawing trees of complexities 1, 2, and 3:

Design and code a recursive algorithm that takes an integer, n, as its parameter and that draws a line-drawing tree of complexity n. Code this algorithm as a method of a subclass of LineDrawing.

Assume as preconditions that n >= 1, that the pen is positioned at the base of the tree’s trunk, and that the pen is heading in the direction the trunk should grow.

Odd Numbers

Design and code a recursive algorithm that takes an integer, n, as its parameter, and outputs all the odd numbers between n and 1, in decreasing order. Note that n can be either odd or even. For example, if n = 5, the algorithm’s output should be

The only precondition for this problem is the trivial one that n is an integer — n may be positive, negative, or zero, and may be either even or odd.

Final Details

The Line Drawing Class

Documentation on the LineDrawing class 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.