CSC 207 CSC 207.01 & .02- Algorithms and Object-Oriented Design Spring 2022 Home Schedule Class Slides Labs Assignments Resources Lab: Recursion This lab will give you practice with recursive methods in Java, using both text in the console and also with the graphical user interface, using DrawingPanel.java. The lab is intended to be a refresher on recursion in preparation for working with the Trees data structures that we will be using in later weeks in this course. Getting Started Create a new Java Project in Eclipse. You will be creating a number of programs during this lab, although they will not be related to one another. You should also import the DrawingPanel.java program located at: /home/johnsonba/csc207/startupcode/DrawingPanel.java Printing a File in Reverse (Recursively) Create a program that will open a Scanner to read a file and print every line in reverse order. You will not use a data structure for this exercise!! Instead, create a recursive method that takes the Scanner as a parameter. For convenience, you may create one file that contains the main method as well as the recursive reverse method. You do not need to read the file name from the command line or as input. You can specify the file name in your program for convenience. Is the recursive function static or non-static? What is the base case for the recursive function? What is the recursive case? Don't forget to open the file in a try ... catch .... finally block!! Fibonnaci Sequence (Recursively) The Fibonnaci sequence is a series of numbers in which each number is the sum of the previous two numbers. For example, the first 8 numbers of the sequence are: 0, 1, 1, 2, 3, 5, 8, 13 .... The series can be calcuated using either iteration or recursion to find the number in the nth position of the sequence. For this lab, use a recursive approach. It is a little more complicated than other recursive methods because the base case for this problem is more complex, and you will need to consider what the recursive method should do when asked to find the Fibonnaci number at positions 0, 1, and 2. The recursive case is also unusual and will require two recursive calls. Your recursive method will NOT PRINT the sequence. It should only calculate the Fibonnaci number for the position, such as 8 for the 6th Fibonnaci number. The sequence given above starts a position 0 = 0, position 1 = 1, position 2 = 1, etc. You can create a single file that contains the recursive method the main method for convenience. Should the recursive method be static or non-static? First consider that the recursive method should return if the position n is either 0, 1, or 2. Arguably, the answer for the Fibonacci number at position 0 is not necessary, but I include it in case a user would call the method with 0 as a parameter, and many listings of the Fibonnaci numbers include it. Then, based on the algorithm for finding a Fibonnaci number (adding the sum of the previous two Fibonnaci numbers), what should the recursive calls be? Remember, there will be two calls in the recursive case, each with a different parameter. At this point, do not try for elegance and use the straight-forward approach to calculating the numbers with two recursive calls. Your main method should ask the user how many Fibonnaci numbers to print. Remember to put the String to Integer conversion in a try ... catch block. Then, your main program should print that many numbers in the Fibonnaci sequence. Use a loop to calculate and then print each Fibonnaci number up to the requested position. The Sierpinsky Triangle (7 points) Fractals are an interesting field of study in computer science that have been gaining popularity with increased ability to draw images using computers. Many of them are easily described using recursion, and we will attempt one today. Note that fractals are defined as infinitely repeating images drawn with slight offsets. For practical reasons, we will put a limit on the number of levels of recursion as we draw something like this image (ignoring the "frame" that was included in my screen capture). Getting Started To get started, import the DrawingPanel.java class we used for the Graphical User Interface lab. Create a drawing panel that is fairly large, such as 400 x 400 or even larger Don't forget to create a Graphics object as well so that you can draw on your drawng panel Customize the background and drawing colors as you like Level 1: Base Case At level 1, we simply want to draw an equilateral triangle on the DrawingPanel. Since triangles are somewhat challenging to draw, start here and make sure you can create a filled triangle before you move on to tackling the recursive cases. You will need to use Java's Polygon class and the addPoint method. So open up the Java documentation now and keep it handy. Create what will become your recursive method. You do not need to submit the answers to these questions, but they are here to guide you in thinking about your code and design. Should this be static or non-static? What is the base case? What are the other parameters your method will need? To draw a triangle in Java, we create a Polygon object that is defined by three points. First create a new Polygon Then, add the three points are are the vertices of the triangle using addPoint(x, y). We are going to fill the drawing panel with most of our Sierpinski Triangle. Calculating the starting points for the vertices is a little complicated, if you have not had trigonometry lately. All of your sides will all be of the same length (let's call it side), and if your triangle's top vertex will be located at the point (side/2, 0), the height of the triangle should be (Math.sqrt(3) * side / 2). Once you have added the points to the polygon, you can draw it using the fillPolygon method from the Graphics class. Test drawing that first triangle using your (not-yet-recursive) drawing method. You should have an equilateral triangle centered in your drawing panel, although it will not quite fill from top to bottom. Level 2: Recursive Calls You will need to write a helper function that finds the midpoint of the line between two vertices. Once you have the helper function written, you will use that to divide the current triangle into three subtriangles, each defined by the midpoints of the lines of the outer triangle There will be three recursive calls to your recursive method, each with one of the subtriangles you have defined. Remember to reduce the level by one for the recursive call so that you do not have an infinite loop. Try drawing the Sierpinski Triangle at level 2. It should look something like this: If your image matches this one, try increasing the number of levels. You will get a nice, lacey image. Lab Submission Submit your file(s) containing the source code for the Sierpinski Triangle Since this a new lab, please also submit an estimate for the amount of time you spent on the lab. Put this in a separate file!! Submit this lab in Gradescope. Acknowledgements Thank you to Stuart Reges and Marty Stepp at the University of Washington who published the DrawingPanel.java class in their book, Building Java Programs. These exercises were adapted from or suggested by the following readings and examples: Guru 99's Fibonnaci series StackOverflow's many examples of how to draw an equilateral triangle in Java Stuart Reges and Marty Stepp. Building Java Programs, 5th edition Weiss's chapter 7 on Recursion This derivative work is used and licensed under a Creative Commons Attribution-NonCommercialShareAlike 4.0 International license. This course is adapted from prior courses taught by Shervin Hajiamini, John Stone, Sam Rebelsky, Anya Vostinar, and Jerod Weinman and used by permission. Other authors' contributions are noted when used or adapted.
