Recursion

Lab 11 -- Recursion

The purpose of this lab is to learn to write recursive methods.

Part 1 - Recursive Functions

For this part, you'll be writing five methods that illustrate the power of recursion. The methods will perform the following operations:

computing n factorial
computing powers of 2
reversing a string
palindrome testing
subsequence matching

All of these methods will be written in an application program called RecFun.java. The main program of the application will call one of the recursive methods, based on the values of its command-line arguments. The first command-line argument will indicate which method to call (e.g., "factorial" for factorial, "pow2" for powers of 2, etc.). The remaining command-line arguments are arguments specific to the method being called, and are described in more detail below. A sample session will look like this:

% java RecFun factorial 3
6
% java RecFun reverse hello
olleh

etc.

Note: Command-line arguments are always passed to your main program as Strings. In the cases where the argument represents an integer, use the method Integer.parseInt(String) to convert the argument to an int. For example, you can use the following statement to get the value of n that you pass to your factorial method.

int n = Integer.parseInt(args[1]);

Now, some details on the specific methods I am asking you to write.

Find n!

Write a method that takes as parameter and integer n and returns the factorial of n without using any loops. The recursive definition of factorial is as follows:

fact(n) =		{	1	if n == 0
			n * fact(n-1)	otherwise

examples:

% java RecNum factorial 4
24
% java RecNum factorial 7
5040

Find the powers of 2 up to n

Write a method that takes as parameter an integer n and returns an ArrayList containing all powers of 2 up to the nth power. Again, use recursion without any loops. The recursive definition of this function is as follows:

pow2(n) =		{	the empty list	if n < 0
			add 2ⁿ to the end of pow2(n-1)	otherwise

examples:

% java RecNum pow2 0
[1]
% java RecNum pow2 3
[1, 2, 4, 8]
% java RecNum pow2 10
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]

Reversing a string

Write a recursive method to reverse the order of the characters in a string. The reverse of a string is just the last character followed by the reverse of the rest of the string (or the first character preceded by the reverse of the rest of the string). As a base case, the reverse of a length-0 or length-1 string is the string itself. That is,

reverse(x) =		{	x	if length(x) <= 1
			remove the first character of x; reverse the remaining string; add the removed character to the end of x;	otherwise

You may want to look up some of java's String methods, such as charAt and substring.

examples

% java RecFun reverse alucard
dracula
% java RecFun reverse alabama
amabala

Palindrome testing

This recursive method should return the boolean value true if the parameter passed in is a palindrome, and false otherwise. By definition, a string is a palindrome if it is equal to its own reverse. You can also test this recursively (and, of course, that's how I want you to do it!). If the first and last characters match, and the inner substring (i.e., with the first and last characters removed) is a palindrome, then the entire string is a palindrome. That is,

pal(x) =		{	true	if length(x) <= 1
			x's first char == x's last char and pal(x with its first and last characters removed)	otherwise

examples

% java RecFun pal never
false
% java RecFun pal ohio
false
% java RecFun pal anagana
true
% java RecFun pal "step on no pets"
true

Subsequence matching

Given two strings s1 and s2, determine whether or not s2 is a subsequence of s1. That is, do the characters of s2 appear in s1 in the correct order, but not necessarily consecutively? I'll let you work out the details on this one, but here are a couple of hints:

As base cases, consider what the result should be if either s1 or s2 is an empty string.
If neither s1 nor s2 is empty, then compare their first characters. If they are the same, you can then use a recursive call to check whether or not the remainder of s2 is a subsequence of the remainder of s1. If they are not the same, make a recursive call to check whether or not all of s2 is a subsequence of the remainder of s1.

examples

% java RecFun subseq recursion recur
true
% java RecFun subseq recursion con
true
% java RecFun subseq recursion run
true
% java RecFun subseq recursion cure
false
% java RecFun subseq recursion soon
false

Part 2 - Drawing Fractal Images

For this part, write a series of programs that will draw fractal images using recursion. Each program will have three command line arguments indicating the width and height of the picture, and the number of levels of recursion to use in the picture. There are four types of drawing:

Bubbles
Sierpinski carpet
Sierpinski gasket
Koch snowflake

You'll need to use the Picture class from earlier labs for this part. I've added a few methods, so you need to download a new version, found in the lab11.jar file.

Drawing some bubbles

square design You can draw a picture with the bubble pattern shown below recursively. The basic strategy is this:

1. Draw a circle in the center of the picture. Its radius should be 1/4 the width of the picture. Use the drawCircleFill method.

2. Then divide the picture into four equal sized areas (A, B, C, and D) as shown in the figure to the right. Recursively draw bubbles in each of the four areas.

You'll need to have a base case to stop the recursion at some point, so that you don't get into an endless series of recursive calls. You can achieve this by setting a limit on the number of levels of recursive calls that your program makes. I suggest writing a method with the signature

public static void drawBubbles(Picture p, int x, int y, int width, int height, int nlevels);

to draw a bubble pattern in the rectangle with (x,y) in the upper left corner, of the given width and height. nlevels represents the number of levels of recursive calls. When you make a recursive call, decrement the value of nlevels that you pass to the method. When the level is 0, just draw a single circle and return.

Call drawBubbles from a main program in a file called Bubbles.java. Bubbles.java has three command-line arguments: the width and height of the picture, and the desired number of recursion levels. The main program should instantiate a Picture of the specified dimensions, draw a background color, and then call drawBubbles to draw the bubble pattern. Don't forget to call picture.display() when you're finished drawing.

The following shows the result with 6 levels of recursion. With zero levels, there will just be a single circle in the middle. Of course, you can use whatever colors you like.

Drawing a carpet

Next, write a program called Carpet.java which draws an image known as Sierpinski's carpet, as shown below:

To create this drawing, divide the work area into a 3x3 grid. Fill in the center section and then draw a Sierpinski carpet (with one fewer recursion levels) in each of the remaining 8 surrounding squares.

You can use the method

drawRectFill(int x, int y, int width, int height);

to draw a rectangle filled with the current color

The picture above shows a Sierpinski carpet of order 5.

As with Bubbles, Carpet.java should accept command-line arguments to indicate the width and height of the picture, and the number of recursion levels.

Drawing a gasket

The next image is known as either Sierpinski's triangle or Sierpinski's gasket. Shown below is a Sierpinski gasket of order 5:

square design You can draw a Sierpinski gasket as follows:

The base case (i.e., levels==0) is simply a triangle drawn inside a rectangle.

To draw a Sierpinski gasket with n recursion levels (n>0), locate 3 equal sized rectangles (A, B, C) within the main rectangle, as shown in the figure to the right. Draw a Sierpinski gasket with (n-1) levels in each of these three rectangles. For this figure, all of the triangles that are drawn are of the same size, so don't draw anything until you get to level 0.

To draw a triangle, you can use the drawPolyFill method of Picture. You pass in an array of x-values, y-values, and a count of the number of points to use. These values represent the x- and y- coordinates of the vertices of the polygon. For example, to draw a filled triangle with vertices (3,4), (5,7), and (6,9), write

        int[] xvals = {3, 5, 6};
        int[] yvals = {4, 7, 9};
        picture.drawPolyFill(xvals, yvals, 3);

Call your program Gasket.java. Use the same command-line arguments as in Bubbles and Carpet.

Drawing a snowflake

The final recursive image you'll be creating is known as the Koch Snowflake. In this one, you'll be drawing a modified equilateral triangle. The recursive method is actually only concerned with drawing one "side" of the triangle, which is called a Koch curve. Once you have the Koch curve working, you can draw a Koch Snowflake with just 3 Koch curves.

A Koch curve from point P to point Q is described recursively as follows:

A Koch curve of order 0 is simply a straight line segment from P to Q.
A Koch curve of order n (n>0) from P to Q is drawn as follows:

Draw a Koch curve of order (n-1) one third of the way from P to Q.
From that point, turn 60 degrees to the right and draw a Koch curve of order (n-1) in that direction. The length of this line should be the same as the previous one.
From that point, turn 120 degrees to the left and draw a Koch curve of order (n-1) in that direction, again of the same length.
From that point, turn back to the original direction and draw a Koch curve of order (n-1) in that direction, again of the same length. You should now be at point Q.

The Koch curves of order 0, 1, 2, and 3 (with direction = 0) look like this:

To draw a Koch curve with the Picture class, you can use a few of its methods that we haven't used before:

void setPosition(double x, double y);	sets the current position of the drawing pen to (x,y).
void setDirection(double angle);	sets the current direction of the drawing pen to the given angle (in degrees). (0 indicates horizontal to the right; positive directions are measured counterclockwise; negative directions are measured clockwise)
void rotate(double angle);	rotates the pen direction by the given number of degrees.
void drawLineForward(double distance);	draws a line of the given distance (in pixels), starting at the current pen position and heading in the current direction.

I suggest that you write a method to draw a Koch curve, with the following signature:

public static void drawKochCurve(Picture p, double length, int levels);

where

p is the Picture to draw in.
length is the distance between the endpoints of the line, in pixels.
levels is the number of recursion levels.

The starting position and direction should be set before calling drawKochCurve the first time.

(Note: The reason for using doubles here is that there tends to be a problem with roundoff error if you perform all of the arithmetic with integers. You should do all of your calculations with doubles.)

Once you have written the drawKochCurve method, you can write a drawKochSnowflake method. It is not recursive. All it needs to do is to draw 3 Koch curves in the shape of an equilateral triangle:

draw the base of the triangle with direction = 0
turn 120 degrees and draw the right side of the triangle
turn 120 degrees and draw the left side of the triangle

Here is an example of the resulting final picture (a Koch snowflake of order 5):

Optional

Do a little experimenting and try to draw your own recursive figure!

handin

The directory you submit should contain the files RecFun.java, Bubbles.java, Carpet.java, Gasket.java, and Snowflake.java. Be sure to write a comment with your name and a brief description of tthe program in each file. Also, if you followed the Honor Code in this assignment, insert a paragraph attesting to this fact in the top comment block of this file as well.