Description
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
-
Start with the file TemplateLab10Bronze.java.
-
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
-
-
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.
-
-
-
Draw 4 lines from the center of the whole area to the centres of each of the 4 quadrants.
-
-
-
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:
-
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.
-
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
-
Start with the file TemplateLab10Gold.java.
-
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.)
-
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.
-
Run the supplied main program which will test your methods for n=1, 2, and 6.