CPSC 170 Lab 6: Recursion and Induction

As usual, create a lab6 subdirectory for today's lab, open this document in Mozilla, and start emacs.

Computing a positive integer power of a number is easily seen as a recursive process:
```
x⁰ = 1
x^y = x*x^y-1  for all y > 1
```
File Power.java contains a main program that reads in integers base and exp and calls method power to compute base^exp. Fill in the code for power to make it a recursive method to do the power computation.
Print Power.java.
The Fibonacci sequence is a well-known mathematical sequence in which each term is the sum of the two previous terms. More specifically, if fib(n) is the nth term of the sequence, then the sequence can be defined as follows:
```
    fib(0) = 0
    fib(1) = 1
    fib(n) = fib(n-1) + fib(n-2)  n>1
```
For example, the first eight elements of the sequence are 0,1,1,2,3,5,8,13.
Because the Fibonacci sequence is defined recursively, it is natural to write a recursive method to determine the nth number in the sequence. File Fib.java contains the skeleton for a program that reads an integer n from and computes and prints the n^th Fibonacci number. Save this file to your directory. Following the specification above, fill in the code for method fib so that it recursively computes and returns the nth number in the sequence.
Print Fib.java.
Printing a string backwards can be done iteratively or recursively. To do it recursively, think of the following specification:
If s contains any characters (i.e., is not the empty string)
- print the last character in s
- print s' backwards, where s' is s without its last character
File Backwards.java contains a program that prompts the user for a string, then calls method printBackwards to print the string backwards. Save this file to your directory and fill in the code for printBackwards using the recursive strategy outlined above. Recall that for a String s in Java,
- s.length() returns the number of charaters in s
- s.charAt(i) returns the i^th character of s, 0-based
- s.substring(i,j) returns the substring that starts with the i^th character of s and ends with the j-1^st character of s (not the j^th!), both 0-based.
So if s="happy", s.length=5, s.charAt(1)=a, and s.substring(2,4) = "pp".
Print Backwards.java.
A palindrome is a string that is the same forward and backward. In Chapter 3 you saw a program that uses a loop to determine whether a string is a palindrome. However, it is also easy to define a palindrome recursively as follows:
- A string containing fewer than 2 letters is always a palindrome.
- A string containing 2 or more letters is a palindrome if
  - its first and last letters are the same, and
  - the rest of the string (without the first and last letters) is also a palindrome.
Write a program that prompts for and reads in a string, then prints a message saying whether it is a palindrome. Your main method should read the string and call a recursive (static) method palindrome that takes a string and returns true if the string is a palindrome, false otherwise.
A fractal is a geometric figure that is self-similar in that any piece of the figure contains a miniature of the entire figure. There are lots of fractals that have interesting mathematical properties (and make pretty pictures); a Sierpinski triangle is a fractal that may be constructed as follows:
1. Draw a triangle.
2. Draw a new triangle by connecting the midpoints of the three sides of your original triangle. This should split your triangle into four smaller triangles, one in the center and three around the outside.
3. Repeat (2) for each of the outside triangles (not the center one). Each of them will split into four yet smaller triangles. Repeat for each of their outside triangles.. and for each of the new ones.. and so on, forever. Draw a few rounds of this on paper to see how it works, then check out the demo to see it on screen. Reload to get another triangle.
Your job is to write a Java program that draws a Sierpinski triangle. Think about the following:
- A Sierpinski triangle is a recursively defined structure -- each of the three outer triangles formed by joining the midpoints is itself a Sierpinski triangle.
- In practice you don't want to go on with the process "forever" as suggested above, so we'll limit how deep it goes. Define the depth of a Sierpinski triangle as the number of directly nested triangles at the deepest point. So a Sierpinski triangle consisting of a single triangle has depth 0; when a triangle is drawn inside of it, the resulting Sierpinski triangle has depth 1; when the three outside triangles have triangles drawn inside of them, the resulting triangle is depth 2, and so on. A depth of 10 or 11 gives a nice looking triangle in a reasonable amount of time. (The demo uses depth 10.) Smaller depths are interesting in that you can see more of the construction; higher depths generally take too long for casual viewing.
- A triangle is a polygon, so you'll use the drawPolygon method. Remember that it takes an array containing the x coordinates, an array containing the y coordinates, and an integer indicating how many points should be drawn (3 for a triangle).
- As usual, you'll need two files: 1) a driver that sets up a JFrame, adds an interesting JPanel to it, and displays it, and 2) the class that defines the JPanel. You can model the driver after ones you've done before, with one modification: instead of calling the pack method of the JFrame, use its setSize method to set the JFrame to slightly larger than the JPanel you will add to it. For example, if your JPanel is 600x400, you might make your JFrame 650x450.
- Most of the work goes on in the class that defines the JPanel:
  - Use instance variables to hold the vertices of the initial triangle and the triangle's color. Initialize these appropriately (choose a random color) in the constructor. For the vertices, I strongly recommend using the Point class (p. 858 in the text), one Point for each vertex. You may be tempted to use an array of x coordinates and an array of y coordinates, since you'll need these to draw the triangle anyway, but it's much cleaner later if you go with Points.
  - Use constants to hold the desired depth and the height and width of the panel.
  - The paintComponent method should draw the initial triangle, then call a recursive sierpinski method, passing it the Graphics object, the points of the initial triangle, and the initial depth (0). It will have to construct arrays of x and y coordinates from the points it was passed to do the drawing, but it should pass the points themselves to sierpinski. The initial triangle should look like the one in the demo -- one point at the top center of the window and one point near each lower corner.
  - The sierpinski method should assume that the triangle whose points were passed in has already been drawn. Its job is to check to see if the desired depth has been achieved; if not, it should draw the triangle formed by the midpoints of the given points (yes, you'll need to form arrays again), then call itself recursively on each of the three new outer triangles. Note that it will have to figure out what points to pass to each of these calls, and that the depth is increased by one in each recursive call.
- Your triangles may look a little different from the demo's as they draw, because the demo is an applet and you are using a JFrame.
When this works, modify it so that when the user clicks, a new, random Sierpinski triangle is drawn. (The demo does this too.) You'll need the usual private inner class to implement the MouseListener interface, and in the mouseClicked method you will need to choose three random points and a random color and repaint. If you followed the guidelines above, nothing will change in your paintComponent or sierpinski methods. (But be sure that paintComponent calls super.paintComponent() as its first statement or it won't erase the previous triangle.)
Print your Sierpinski program.