CS 163/164, Fall 2016

Lab 17 - Practicing Recursion

Mon-Wed, Nov. 7-9, 2016

Objectives of this Lab

1. To practice using recursion to implement several methods, and
2. to make some pictures of a Sierpinski triangle.

Description

Follow the steps exactly in their order:

1. Make an Eclipse project named R17.
2. Download Recursion.java, Triangle.java and UserInterface.java to your project.
3. Implement the computeFactorial() method, as follows:
• Implement the base case by returning 1 when the number is 0 or 1.
• The recursive case returns the number multiplied by the return value from computeFactorial, called with one less than the number.
• Test the method using the code provided in the main method.
• Check your answers by looking at the Wikipedia web page on factorials here.
4. Implement the geometricSeries() method, as follows:
• Implement the base case by returning 0.0 when the number of terms is 0.
• Next compute the return value as the quotient of the numerator and denominator.
• Next call the method recursively with the same numerator, the denominator multiplied by 2, and number of terms minus 1.
• Add the return value from the method to the return value and return it.
• Test the method using the code provided in the main method.
• Check your answers by looking at the Wikipedia web page on geometric series here.
5. Implement the sierpinski() method, as follows:
• Implement the base case by returning when the number of levels is 0.
• Compute the midpoints of each side of the triangle, into the variables shown.
• Construct one inside triangle from the midpoints, and add it to the array list.
• HINT: Always construct triangles with the top, left, and right points, in that order.
• You have been given an example of constructing a triangle and adding it in the supplied code.
• Construct three outside triangle from the original points and midpoints.
• Add the outside triangles in the following order: top, left, and right.
• Recursively call the sierpinski method with each of the outside triangles, and the number of levels minus 1.
• When you run the main method in Recursion, it will display all triangles.
• The output below shows the correct number of triangles based on the number of levels.

        Sierpinski Triangle, number of levels: 1
        Triangles generated: 4
        Sierpinski Triangle, number of levels: 2
        Triangles generated: 16
        Sierpinski Triangle, number of levels: 3
        Triangles generated: 52
        Sierpinski Triangle, number of levels: 4
        Triangles generated: 160
        Sierpinski Triangle, number of levels: 5
        Triangles generated: 484
        

• Here is an image that shows the coordinates when subdividing the first level Sierpinski triangle:
  
  
  
  
6. Use the main method in Recursion.java to test all of your code.

Grading Criteria

• 100 points for perfect submission.
• 0 points for no submission, will not compile, submitted class file, etc.
• Preliminary Tests:
  • compileTest: checks that Recursion.java program compiles. (0 points)
  • checkFactorial0: Checks the factorial computation for the number 0. (5 points)
  • checkFactorial1: Checks the factorial computation for the number 1. (5 points)
  • checkFactorial2: Checks the factorial computation for the number 2. (5 points)
  • checkFactorial3: Checks the factorial computation for the number 3. (5 points)
  • checkFactorial4: Checks the factorial computation for the number 4. (5 points)
  • checkFactorial5: Checks the factorial computation for the number 5. (5 points)
  • checkFactorial10: Checks the factorial computation for the number 10. (5 points)
  • checkGeometric1: Checks the sum of the geometric series with 1 term. (5 points)
  • checkGeometric2: Checks the sum of the geometric series with 2 terms. (5 points)
  • checkGeometric3: Checks the sum of the geometric series with 3 terms. (5 points)
  • checkGeometric4: Checks the sum of the geometric series with 4 terms. (5 points)
  • checkGeometric5: Checks the sum of the geometric series with 5 terms. (5 points)
  • checkGeometric10: Checks the sum of the geometric series with 10 terms. (5 points)
  • checkGeometric20: Checks the sum of the geometric series with 20 terms. (5 points)
  • checkSierpinski1: Checks the triangles in a Sierpinski triangle with 1 level. (5 points)
  • checkSierpinski2: Checks the triangles in a Sierpinski triangle with 2 levels. (5 points)
  • checkSierpinski3: Checks the triangles in a Sierpinski triangle with 3 levels. (5 points)
  • checkSierpinski4: Checks the triangles in a Sierpinski triangle with 4 levels. (5 points)
  • checkSierpinski5: Checks the triangles in a Sierpinski triangle with 5 levels. (10 points)
• Final grading is identical to the preliminary tests.

---