MATERIAL COVERED
Recursion
Notes:
The three exercises in this lab are independent – they can be done in any order. Only one of the three exercises is required, but try to do as many as you can.
The Silver exercise requires StdDraw.
A simple recursion
1. Start with the file TemplateLab10Bronze.java.
2. Add a recursive method double largestInList(int n, double[] list) which will find the
largest of the first n elements of the array of doubles list . Assume n is between 1 and list.length. You must use recursion to do this – no loop of any kind is allowed.
Fractal graphics
A fractal image is one which is made up of smaller versions of the same image. Here’s how to create a simple fractal image:
To make a “level n” image in a square area
a. divide it into four smaller “quadrants”: the upper left, upper right, lower left, and lower right – all square areas taking up exactly ¼ of the original area each.
b. Draw 4 lines from the center of the whole area to the centres of each of the 4 quadrants.
c. Draw “level n-1” fractal images in each of the four quadrants, in exactly the same way. A “level 1” image is the smallest. A “level 0” image doesn’t draw anything at all.
Here are pictures of level 1-3 images:
1. Start with the file TemplateLab10Silver.java.
2. Complete the recursive method void drawFractal(double xMin, double xMax, double yMin, double yMax, int nLevels) which will draw a fractal image, of level nLevels, in the rectangular
area specified by the other four parameters.
3. Run the supplied main method. You can click the mouse button in the StdDraw window to advance from one level of fractal to the next, from level 1 up to level 8.
Integer sums
This is a very challenging question. Good luck!
There are 11 different ways to write a sum of positive integers (greater than 0) that add up to 6, if the integers are in descending order:
6
5+1
4+2
4+1+1
3+3
3+2+1
3+1+1+1
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1
1. Start with the file TemplateLab10Gold.java.
2. Complete the method void printAllSums(int n) which will print all of the ways to write a sum of
positive integers that add up to n, exactly as shown above (for n=6). This method will not be recursive itself. It should simply call the one below. (It should be a 1-line method.)
3. Create a more general recursive version of printAllSums, with an extra parameter or two, which will allow the sums to be easily computed and printed. The single-parameter version above should call this one. Note that this will be a very short method, but it may be difficult to figure out how to do it. Look at the patterns in the example above and try to spot a simple recursion. Good luck.
4. Run the supplied main program which will test your methods for n=1, 2, and 6.
