1. |
The factorial of a positive integer is the product of all nonnegative integers less than or equal to that number. (The symbol for factorial is "!" - the exclamation mark.) The formula for factorials for all nonnegative integers is: n! = n * (n-1)! for n > 0; Zero
factorial is a special case and 0! = 1 From
this definition, 5! is 120: Write
a recursive factorial method long factorial(int n) |

2. |
You
can also compute the factorial values iteratively, without using
recursion. Supply a non-recursive factorial method. |

3. |
Write a tester class that tests both solutions. |

4. |
A formula for finding the greatest common divisor (GCD) of two numbers was formulated by the mathematician Euclid around 300 BCE. The GCD of two numbers is the largest number that will divide into both numbers without any remainder. For example, the GCD of 12 and 16 is 4, the GCD of 18 and 12 is 6. The basic algorithm is as follows: Let
Let
If
Otherwise,
the GCD of Recall
that in Java, the 16 % 12 = 4Now you need to compute the GCD of 12 and 4. 12 % 4 = 0Therefore, the GCD is 4. Write
a recursive method that finds the GCD of two numbers using Euclid's
algorithm. (You may assume--or, better, assert--that both inputs are
positive.) |

5. |
Write a tester program for your GCD class. |

6. |
Write a program to draw the logarithmic spiral recursively. The logarithmic spiral or Fibonacci spiral is a shape often found in nature. The nautilus shell is the classic example of the logarithmic spiral. Seed patterns in sunflowers and pinecones also demonstrate the spiral.
To construct a logarithmic spiral, begin with a "golden" rectangle. A golden rectangle is a rectangle with sides of length A and φA, where φ (Phi) is the golden mean or the value ( 1 + sqrt(5) ) / 2 or 1.61803 . . . A square with length equal to the smallest side of the rectangle is drawn inside the rectangle. A quarter arc (arcAngle = 90 degrees) is drawn within this square. The remaining rectangle is also a golden rectangle. This remaining rectangle is divided into a square and another smaller golden rectangle. A quarter arc connected to the previous arc is drawn inside the square, and the remaining rectangle is once again subdivided with an arc drawn in it. Create a panel in which to draw the spiral: public class LogSpiralPanel extends JPanel Given
the dimensions of the panel, draw the largest golden rectangle
that will fit within the panel. Part of the code of the class has been
provided for you: import
java.awt.Graphics2D;
import java.awt.Graphics; import java.awt.Rectangle; import java.awt.geom.Arc2D; import javax.swing.JPanel; public class LogSpiralPanel extends JPanel { public void paintComponent(Graphics g) { Graphics2D g2 = (Graphics2D) g; /* Your code goes here. 1. create the goldenRectangle (you can use getHeight() to obtain the side size 2. draw the golden rectangle 3. call the recursive helper method "recursiveDraw" which will draw the spiral */ }
/**
Method that recursively draws a logarithmic spiral. @param x The upper left corner x-coordinate of the golden rectangle @param y The upper left corner y-coordinate of the golden rectangle @param side the smallest side size of the golden rectangle @param angle the angle (0, 90, 180 or 270) where the top of the golden rectangle is located. For the outermost golden rectangle, the angle is 90. */ private void recursiveDraw(Graphics2D g2, double x, double y, double side, int angle) { // we'll do this in the next section. . . }
private static
final double GOLDEN_MEAN = (1 + Math.sqrt(5)) / 2;
} What is the code of your completed paintComponent method? |

7. |
Now you will complete the code of the recursive helper method recursiveDraw. To recursively draw the logarithmic spiral, you first need to draw the square. The square's upper-left corner is at position (x, y), and its side size is side. Then you need to draw the arc. You can use the method drawArc that has been provided for you. Then you need to recursively call recursiveDraw to continue drawing the spiral recursively. Before making the recursive call you need to calculate the new side size, the new x-coordinate, the new y-coordinate and the new angle. Two methods calculateNewX and calculateNewY have been provided for you. You can use these methods to calculate the new x and y coordinate, but you need to calculate the new side size and the new angle yourself. Remember that the new side size is the difference between the sizes of the two sides of the current rectangle. The new angle is given by rotating the current angle 90 degrees in clock-wise direction. public class LogSpiralPanel extends JPanel { public void paintComponent(Graphics g) { . . . } /** Method that recursively draws a logarithmic spiral. @param x The upper left corner x-coordinate of the golden rectangle @param y The upper left corder y-coordinate of the golden rectangle @param side the smallest side size of the golden rectangle @param angle The angle (0, 90, 180 or 270) where the top of the current golden rectangle is located. For the outermost golden rectangle, the angle is 90. */ private void recursiveDraw(Graphics2D g2, double x, double y, double side, int angle) { /* Recursion ending condition: when the side is very small */ . . . /* Draw the current square and arc */ . . . /* Continue drawing the spiral recursively: calculate the new side size, calculate the new (x, y) coordinates and the new angle. Then, call "recursiveDraw" again. */ . . . } /** Draws the arc of the current iteration. @param x The upper-left corner x-coordinate of the square @param y The upper-left corner y-coordinate of the square @param side The size of the side of the square (or the arc's radius) @param angle The angle (0, 90, 180 or 270) where the top of the current golden rectangle is located. For the outermost golden rectangle, the angle is 90. */ private void drawArc(Graphics2D g2, double x, double y, double side, int angle) { double auxX = x; double auxY = y; if (angle == 0 || angle == 270) auxX = x - side; if (angle == 270 || angle == 180) auxY = y - side; Rectangle2D.Double boundingRectangle = new Rectangle2D.Double(auxX, auxY, side * 2, side * 2); Arc2D.Double arc = new Arc2D.Double(boundingRectangle, angle, 90, Arc2D.OPEN); g2.draw(arc); } private double calculateNewX(double x, double angle, double side, double newSide) { if (angle == 0) x = x + side - newSide; else if (angle == 90) x = x + side; else if (angle == 270) x = x - newSide; return x; } private double calculateNewY(double y, double angle, double side, double newSide) { if (angle == 0) y = y + side; else if (angle == 180) y = y - newSide; else if (angle == 270) y = y + side - newSide; return y; } private static final double GOLDEN_MEAN = (1 + Math.sqrt(5)) / 2; } What is the code of your recursiveDraw method? |

8. |
Create
a LogSpiralFrame
class that will contain the LogSpiralPanel. What is
the code of your class? |

9. |
What is the code of your viewer class? |

10. |
The golden mean, often referred to as the golden ratio, divine proportion, or the golden number is represented by the Greek letter phi (φ). The value of the golden mean is (1 + sqrt(5)) / 2 or 1.61803 . . . The golden mean is found in nature and art and tends to yield the most "aesthetically pleasing" arrangements of objects. Fibonacci numbers are directly related to the golden mean. The definition of Fibonacci numbers is fib(1) = 1 fib(2) = 1 fib(n) = (fib(n-1) + fib(n-2))
After the first two numbers, each of which has the value of 1, the next number in the Fibonacci sequence is the sum of the two preceding numbers. Computing ratios of Fibonacci numbers can approximate the value of the golden mean. The value of. g(n) = fib(n) / fib(n-1) approximates the golden mean as n goes to infinity. These values can be computed recursively as well. Note that g(n) = (fib(n - 1) + fib(n - 2)) / fib (n - 1)Simplify this expression so that g(n) is expressed in terms
of g(n - 1).(a)
What is your recursive definition for |

11. |
Write
a recursive method that computes the |

12. |
What
is the tenth approximation of the golden ratio? |

13. |
As
you learned in the textbook, the recursive computation of |

14. |
In one variant of the game of Nim, two players alternately take marbles from a pile. In each move, a player chooses how many marbles to take. The player must take at least one but at most half of the marbles. Then the other player takes a turn. The player who is left with one marble loses. Clearly,
if you start with two marbles, you are going to win. Take one marble,
and your opponent loses right away. We therefore say that 2 is a In
general, a winning position is a position in which you can force a win.
That is, there is at least one move that leads to a losing position. Conversely,
a Following
these definitions, write mutually recursive methods
{ for (int i = 1; i <= n / 2; i++) . . .
What is the code for your methods? |

15. |
Run
a test program.Which values between 2 and 100 are losing positions? |

16. |
Why
does this recursion run so slowly? Add trace messages to find out. |

17. |
You
can speed up the methods by remembering for which numbers you have
already determined the answers. Use an array to store known positions.
Here, What is the code for your modified |

18. |
Now run your program again. Just print out the losing positions < 10000. What pattern do you see? |