• gcd(x, x) = x
• For x > y , gcd(x, y) = gcd(x - y, y)
• For y > x , gcd(y, x) = gcd(x, y - x)
19. Turn to lesson page 15-1 of the ProgramLive CD and click the project icon.
You will see a project called Link extractor. This project is to build a Java appli-
cation that produces a list of all links on a website. A recursive procedure is used
to process the graph of web pages that are reachable from a given root. Do this
20. Recursive procedures are great for drawing geometric shapes that are repeat-
ed and drawn at increasingly smaller scales. Such shapes are called fractals . One
example of a fractal is the Koch snowflake, due to a Swedish mathematician
Helge von Koch. In the diagram on the left below is a Koch snowflake of order
0, an equilateral triangle.
The middle figure is a Koch snowflake of order 1. In each of the lines in the
order-1 snowflake, the middle third of the line has been replaced by two sides of
an equilateral triangle. In the order-2 snowflake on the right, again, the middle
part of each line of the order-1 triangle has been replaced by two sides of an equi-
lateral triangle. This process can go to any depth.
Write a procedure to draw a Koch snowflake of order k. You will have to put
this procedure in a class that has a method paint —either a subclass of JFrame
or a JPanel . Your instructor will give you details on this.
Here is the specification of the snowflake procedure.
/** Draw Koch line of order k(≥0) from (x1, y2) to (x5, y5) using g .
public void drawFlakeLine( int k, int x1, int y1,
int x5, int y5, Graphics g)
For k=0 , the Koch line is simply a line from (x1, y2) to (x5, y5) .
For k>0 , the Koch line is 4 Koch lines of order k-1 , drawn as shown here:
Let dx = x5 - x1 , dy = y5 - y1 , and p = sqrt(3.0) / 6. Then: