Big Java / Java Concepts Lab 18

Recursion

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:

1! = 1 * 0! = 1
2! = 2 * 1! = 2
3! = 3 * 2! = 6
4! = 4 * 3! = 24
5! = 5 * 4! = 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 a be the larger, b the smaller number. (We will assume that both values are positive.)

Let c be the remainder that is obtained after dividing a through b.

If c is zero, then the GCD is b.

Otherwise, the GCD of a and b is the same as the GCD of b and c.

Recall that in Java, the % operator computes the remainder. For example, to compute the GCD of 12 and 16, you compute

16 % 12 = 4
Now you need to compute the GCD of 12 and 4.
12 % 4 = 0
Therefore, 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.

Recursive Helper Methods

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?

The Efficiency of Recursion

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 g(n)?
(b) When does the recursion stop?


11.

Write a recursive method that computes the nth iteration of the golden ratio. What is the code of your method?


12.

What is the tenth approximation of the golden ratio?

13.

As you learned in the textbook, the recursive computation of fib(n) can be inefficient. Add trace statements to verify that your method for computing g(n) does not calculate each number more than once. What is the output of your trace messages?

Mutual Recursion (and More Efficiency)

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 winning position.

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 losing position is a position that is either an outright loss, or in which every move leads to a winning position.

Following these definitions, write mutually recursive methods

public class NimCalculator
{
   public boolean isWinningPosition(int n)

   {
      for (int i = 1; i <= n / 2; i++)
         . . .

   }
   public boolean isLosingPosition(int n)
{ . . . }
}

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.

public class NimCalculator
{
   public boolean isWinningPosition(int n) { . . . }
   public boolean isLosingPosition(int n) { . . . }
   private int[] knownPositions = new int[10000];

}

Here, knownPosition[i] should be 1 if i is known to be a winning position, and -1 if i is known to be a losing position, and 0 if it is not known to be either.

What is the code for your modified isWinningPosition and isLosingPosition methods?


18.

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